On the connectivity function of a binary matroid^{∗}

Manoel Lemos Departamento de Matemática Universidade Federal de Pernambuco Cidade Universitária Recife, PE, 50740-540, Brazil

e-mail: manoel@dmat.ufpe.br

Abstract

In this paper, we shall consider the following problem: up to duality, is a connected matroid reconstructible from its connectivity function? Cunningham conjectured that this question has an affirmative answer, but Seymour gave a counter-example for it. In the same paper, Seymour proved that a connected binary matroid is always reconstructible from its connectivity function, up to duality, in the class of binary matroids. In this paper, we prove that when M is a connected binary matroid and N another matroid with the same connectivity function as N, then M = N or M = N^{∗}.

Also, we shall discuss the implications of ours results on the following problem: when it exists, is the decomposition of the rank function of a 2-polimatroid as the sum of the rank functions of matroids unique?

1 Introduction

The matroid theory terminology used in this paper will follow Oxley [7]. The connectivity function of a matroid M is defined as

ξ_{M}(X, Y) = r_{M}(X) + r_{M}(Y) − r(M) + 1,

where {X, Y } is a partition of E(M). This function is invariant under duality, since it may be written as

ξ_{M}(X, Y) = r_{M}(X) + r_{M^{∗}}(X) − |X| + 1.

∗Research partially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq, Brazil).

In particular, a matroid and its dual have the same connectivity function. When M = M_{1} ⊕ M_{2}, then

ξ_{M}(X, Y) + 1 = ξ_{M_{1}}(X ∩ E(M_{1}), Y ∩ E(M_{1})) + ξ_{M_{2}}(X ∩ E(M_{2}), Y ∩ E(M_{2})).

Thus, M_{1} ⊕ M_{2} and M_{1} ⊕ M_{2}^{∗} have the same connectivity function.

In this paper, we shall study matroids with the same connectivity function. By the last identity, we may restrict our attention to connected matroids. In this case, Cunningham conjectured that, up to duality, a connected matroid is reconstructed from its connectivity function, that is:

Cunningham conjecture. If M and N are connected matroids on the same ground set having the same connectivity function, then M = N or M = N^{∗}.

In [11], Seymour proved the Cunningham conjecture for the class of binary matroids, that is:

Theorem 1. (3.3 of Seymour[11]) If M and N are connected binary matroids on the same ground set having the same connectivity function, then N = M or N = M^{∗}.

In the same paper, Seymour gave a counter-example for it in general. In [1], Lemos proved that this conjecture is true provided that r(M) ≠ r(M^{∗}). In this paper, we shall prove that a connected binary matroid is reconstructible, not only in the class of binary matroids, but in the class of all matroids. Our main result is:

Theorem 2. Suppose that M is a connected binary matroid. If N is a matroid having the same connectivity function as M and E(N) = E(M), then N = M or N = M^{∗}.

Note that

r_{M}(X) + r_{M^{∗}}(X) = r_{N}(X) + r_{N^{∗}}(X),

for every X ⊆ E, when M and N are matroids over the same ground set E having the same connectivity function. In general, we say that M = (M_{1}, M_{2}, M_{3}, M_{4}) is a quad when M_{1}, M_{2}, M_{3} and M_{4} are matroids over the same ground set, which is denoted by E(M), such that

r_{M_{1}}(X) + r_{M_{2}}(X) = r_{M_{3}}(X) + r_{M_{4}}(X),

for every X ⊆ E(M).

As one can guess from the definition of quads, this problem is related to the following problem which was proposed by Murty and Simon [6]: characterize polimatroid rank functions which are sums of rank functions of matroids? We also may ask: when this decomposition exists is it unique? It follows from ours results that a connected 2-polimatroid that is decomposed as the sum of rank functions of two binary matroids M_{1} and M_{2} cannot have another decomposition as the sum of rank functions of two other matroids M_{3} and M_{4}, unless (M_{1}, M_{2}, M_{3}, M_{4}) is a well described quad. Moreover, when the decomposition is not unique, then there is only two ways of doing it. In [1], Lemos proved that the decomposition of the rank function ρ of a connected 2-polimatroid, defined on E, as the sum of the rank function of two matroids is unique, when it exists, provided that ρ(E) is odd. We shall settle the problem of uniqueness of decomposition of the rank function of a connected 2-polimatroid in another paper, using the theory developed here.

We are setting a different notation from Lemos [1] to get a more compact description of the results. When X denotes a quad, X_{i} denotes the i-th coordinate of this quad, for i ∈ {1, 2, 3, 4}.

We say that two quads M and N are equivalent, and denote this by M ≡ N, when

{{M_{1}, M_{2}}, {M_{3}, M_{4}}} = {{N_{1}, N_{2}}, {N_{3}, N_{4}}}.

We say that two quads M and N are isomorphic, and denote this by M ≃ N, when there is a quad H such that H ≡ M and a bijection f : E(H) → E(N) such that f is an isomorphism between H_{i} and N_{i}, for every i ∈ {1, 2, 3, 4}.

For a quad M and disjoint subsets X and Y of E(M), we define a minor of M as

M\X/Y = (M_{1}\X/Y, M_{2}\X/Y, M_{3}\X/Y, M_{4}\X/Y)

and the dual of M as M^{∗} = (M_{1}^{∗}, M_{2}^{∗}, M_{3}^{∗}, M_{4}^{∗}). We shall use M|X to denote M\(E(M) \ X). In [1], Lemos have proved that

(1.1) (1.1, 1.2 and 1.3 of [1]) M\X/Y and M^{∗} are quads.

When M and N are quads such that E(M)∩E(N) = ∅, we denote by M⊕N the quad

(M_{1} ⊕ N_{1}, M_{2} ⊕ N_{2}, M_{3} ⊕ N_{3}, M_{4} ⊕ N_{4}).

Case N_{1} = N_{2} = N_{3} = N_{4} = N, M ⊕ N is also denoted by M ⊕ N. For a matroid N such that E(N) ∩ E(M) = {e}, M ⊕_{2} N denotes

(M_{1} ⊕_{2} N, M_{2} ⊕_{2} N, M_{3} ⊕_{2} N, M_{4} ⊕_{2} N),

which was proved to be a quad by Lemos in [1].

In [1], Lemos proved the next result which characterizes a quad and it was proved by Seymour for a class of quads, in [11]:

(1.2) (1.4 and 1.5 of [1]) Suppose that M_{i} is a matroid having E as its ground set, for every i ∈ {1, 2, 3, 4}. (M_{1}, M_{2}, M_{3}, M_{4}) is a quad if and only if

C(M_{1}) ∪ C(M_{2}) = C(M_{3}) ∪ C(M_{4}) and C(M_{1}) ∩ C(M_{2}) = C(M_{3}) ∩ C(M_{4}).

Now, we outline the proof of theorem 2: when M and N satisfies the hypothesis of theorem 2 and its conclusion does not hold, then (M, M^{∗}, N, N^{∗}) belongs to the class S of quads M satisfying: M_{1} ≠ M_{3}, M_{1} ≠ M_{4} and both M_{1} and M_{2} binary matroids. The “irreducible” quads of S shall be constructed in section four and all of them have exactly one disconnected matroid as one of its coordinates. So, none of them can be equivalent to (M, M^{∗}, N, N^{∗}). The construction of the “irreducible” quads of S shall be done by induction and the splitter-type theorem for quads is fundamental in this construction — its statement and proof can be found in section three: essentially, it says that an “irreducible” quad can be obtained from a well described “irreducible” quad by a sequence of one element lift or extension without leaving the class of “irreducible” quads.

2 Connectivity results for quads

In this section, we shall prove some connectivity results for quads which will be fundamental in the proof of the splitter-type theorem for quads which shall be presented in the next section. Here, the notions of connectivity and 3connectivity for matroids are extended for quads.

Let M be a quad. For a partition {X, Y } of E(M), we denote by

ξ_{M}(X, Y) = ξ_{M_{1}}(X, Y) + ξ_{M_{2}}(X, Y) = ξ_{M_{3}}(X, Y) + ξ_{M_{4}}(X, Y).

When ξ_{M}(X, Y) = 2, then M = (M|X) ⊕ (M|Y). So, we can restrict our attention to quads satisfying ξ_{M}(X, Y) ≥ 3, for every partition {X, Y } of E(M) such that min{|X|, |Y |} ≥ 1. Such quads are called connected. A quad M is said to be non-trivial, when {M_{1}, M_{2}} ≠ {M_{3}, M_{4}}. In [1], Lemos proved the following result:

(2.1) Suppose that M is a non-trivial connected quad. Then,

(i) (2.6 of [1]) ξ_{M}(X, Y) ≥ 4, for every partition {X, Y } of M such that min{|X|, |Y |} ≥ 1.

(ii) (2.7 of [1]) When ξ_{M_{1}}(X, Y) = ξ_{M_{2}}(X, Y) = ξ_{M_{3}}(X, Y) = ξ_{M_{4}}(X, Y) = 2, for a partition {X, Y } of E(M) such that min{|X|, |Y |} ≥ 2, then there is a matroid N such that E(N) = X ∪ {e} or E(N) = Y ∪ {e}, for an element e ∉ E(M), and a quad N such that E(N) = (E(M)\E(N))∪{e} satisfying M = N ⊕_{2} N.

As a consequence of (2.1)(i), we have the following:

(2.2) If M is a non-trivial connected quad, then M_{i} is both loopless and coloopless, for every i ∈ {1, 2, 3, 4}.

This is a particular instance of a more general result of Lemos [1]:

(2.3) (2.3 of [1]) Let M be a connected quad. If {X, Y } is a 1-separation for both M_{1} and M_{3} such that M_{1}|X = M_{3}|X, then M is trivial.

(2.4) (theorem 2 of [1]) If M is a non-trivial connected quad, then

r(M_{1}) = r(M_{2}) = r(M_{3}) = r(M_{4}).

By this theorem, for a non-trivial connected quad M, we can define its rank, which is denoted by r(M), as the rank of M_{i}, for i ∈ {1, 2, 3, 4}.

We say that {X, Y } is a k-separation for a quad M, when {X, Y } is an exact k-separation for M_{i}, for every i ∈ {1, 2, 3, 4}. By (2.1)(ii), when, {X, Y } is a 2-separation for a non-trivial connected quad M, then M = N ⊕_{2} N, where N is a non-trivial quad and N is a matroid such that E(N) = Z ∪ {e} and e ∈ E(N) ∩ E(N), for some Z ∈ {X, Y }. We say that Z is the dead set associated with the 2-separation {X, Y }. A quad is said to be irreducible, when it does not have a 1-separation or a 2-separation. Observe that the deletion or the contraction of an element of an irreducible quad gives a connected quad.

(2.5) Let M be a non-trivial connected quad. If {X, Y } is a 2-separation for M, then, for every Z ∈ {X, Y }, we have that

r_{M_{1}}(Z) = r_{M_{2}}(Z) = r_{M_{3}}(Z) = r_{M_{4}}(Z).

Moreover, when |X| = 2, X is contained in a series class of M_{i}, for every i ∈ {1, 2, 3, 4}, or X is contained in a parallel class of M_{i}, for every i ∈ {1, 2, 3, 4}.

Proof: Without loss of generality, we may suppose that Y is the dead set of this 2-separation. Thus r_{M_{1}}(Y) = r_{M_{2}}(Y) = r_{M_{3}}(Y) = r_{M_{4}}(Y). Hence r_{M_{1}}(X) = r_{M_{2}}(X) = r_{M_{3}}(X) = r_{M_{4}}(X), because r_{M_{i}}(X) + r_{M_{i}}(Y) − r(M_{i}) = 1 and r(M_{i}) = r(M), for every i ∈ {1, 2, 3, 4}. Moreover, when |X| = 2, X is independent in all these matroids or X is dependent in all these matroids and the result follows.

(2.6) If {X_{1}, Y_{1}} and {X_{2}, Y_{2}} are different 2-separations for a non-trivial connected quad M such that X_{1} and X_{2} are maximal dead sets, then X_{1} ∩X_{2} = ∅.

Proof: Suppose that X_{1} ∩ X_{2} ≠ ∅. Since both X_{1} and X_{2} are maximal dead sets, we have that Y_{1} ∩ X_{2} ≠ ∅ and X_{1} ∩ Y_{2} ≠ ∅.

For i ∈ {1, 2}, as X_{i} is a dead set, it follows that M = N_{i} ⊕_{2} N_{i}, where N_{i} = (N_{i1}, N_{i2}, N_{i3}, N_{i4}) is a quad such that E(N_{i}) = Y_{i} ∪ {e_{i}} and N_{i} is a matroid such that E(N_{i}) = X_{i} ∪ {e_{i}}.

First, we shall prove also that Y_{1} ∩ Y_{2} ≠ ∅. Suppose that Y_{1} ∩ Y_{2} = ∅. In this case, we shall prove that M_{i} = M_{j}, for every i and j such that {i, j} ⊂ {1, 2, 3, 4}, and we arrive at a contradiction. To demonstrate this, by symmetry, it is enough to prove that every circuit C of M_{i} is also a circuit of M_{j}. We may suppose that C ∩ Y_{k} ≠ ∅, for both k ∈ {1, 2}, otherwise C is a circuit of N_{k}\e_{k}, and hence C would be also a circuit of M_{j}. For k ∈ {1, 2}, it follows that (C ∩ X_{k}) ∪ {e_{k}} is a circuit of N_{k}. Hence, there is a circuit C′ of M_{j} such that C′ ∩ X_{1} = C ∩ X_{1} and C′ ∩ Y_{1} ≠ ∅. As Y_{2} ⊆ X_{1} and C ∩ Y_{2} ≠ ∅, it follows that (C′ ∩ Y_{2}) ∪ {e_{2}} = (C ∩ Y_{2}) ∪ {e_{2}} is a circuit of N_{2j}. Since (C ∩ X_{2}) ∪ {e_{2}} is a circuit of N_{2}, we have that C = (C ∩ Y_{2}) ∪ (C ∩ X_{2}) is a circuit of M_{j}. So, Y_{1} ∩ Y_{2} ≠ ∅.

For i ∈ {1, 2}, we set {Z_{i}, W_{i}} = {X_{i}, Y_{i}}. Using submodularity, we arrive at the following:

ξ_{M_{k}}(Z_{1}∩Z_{2}, W_{1}∪W_{2})+ξ_{M_{k}}(Z_{1}∪Z_{2}, W_{1}∩W_{2}) ≤ ξ_{M_{k}}(X_{1}, Y_{1})+ξ_{M_{K}} (X_{2}, Y_{2}) = 4,

for every k ∈ {1, 2, 3, 4}. Thus, for F = {X_{1} ∩ X_{2}, X_{1} ∩ Y_{2}, Y_{1} ∩ X_{2}, Y_{2} ∩ X_{2}},

∑_{Z∈F} ξ_{M_{k}}(Z, E(M) \ Z) ≤ 8.  (1)

By (2.1)(i), for every {i, j} equal to {1, 2} or {3, 4},

ξ_{M_{i}}(Z_{1} ∩ Z_{2}, W_{1} ∪ W_{2}) + ξ_{M_{j}}(Z_{1} ∩ Z_{2}, W_{1} ∪ W_{2}) ≥ 4.

When, we take the sum over F, we get

∑_{Z∈F} ξ_{M_{i}}(Z, E(M) \ Z) + ∑_{Z∈F} ξ_{M_{j}}(Z, E(M) \ Z) ≥ 16.  (2)

Hence, we have equalities in (1) and (2). So, for every k ∈ {1, 2, 3, 4},

ξ_{M_{k}}(Z_{1} ∩ Z_{2}, W_{1} ∪ W_{2}) = 1 + s_{k} and ξ_{M_{k}}(Z_{1} ∪ Z_{2}, W_{1} ∩ W_{2}) = 3 − s_{k}, (3)

for some s_{k} ∈ {0, 1, 2}.

In this paragraph, we shall prove that |Z| = 1 or {Z, E(M) \ Z} is a 2separation for M, for every set Z ∈ F. Suppose that |Z| > 1 and that {Z, E(M) \ Z} is not a 2-separation for M_{k}, say k = 1, for some Z ∈ F. Without loss of generality, by (3), we may suppose that Z = Z_{1} ∩ Z_{2} and that ξ_{M_{1}}(Z_{1} ∩ Z_{2}, W_{1} ∪ W_{2}) = 3. Thus, by (3), ξ_{M_{1}}(Z_{1} ∪ Z_{2}, W_{1} ∩ W_{2}) = 1. Hence W_{1} ∩ W_{2} = Y_{1} ∩ Y_{2}, otherwise {W_{1} ∩ W_{2}, E(N_{i}) \ (W_{1} ∩ W_{2})} is a 1-separation for N_{i}, where i ∈ {1, 2} satisfies X_{i} = W_{i}, and M is not connected. As M is non-trivial and connected, we have that ξ_{M_{2}}(X_{1} ∪ X_{2}, Y_{1} ∩ Y_{2}) = 3, by (2.1)(i). So, by (3), ξ_{M_{2}}(X_{1} ∩ X_{2}, Y_{1} ∪ Y_{2}) = 1 and we arrive at a contradiction because {X_{1} ∩ X_{2}, E(N_{i}) \ (X_{1} ∩ X_{2})} is a 1-separation for N_{i} for both i ∈ {1, 2}.

We can use all the 2-separations found in the previous paragraph to decompose each M_{i}. So, there is a set E = {e_{Z} : Z ∈ F} such that |E| = 4 and E∩E(M) = ∅, and there are matroids K_{iZ} and J_{i} such that E(K_{iZ}) = Z∪{e_{Z}}, E(J_{i}) = E and

M_{i} = J_{i} ⊕_{2} K_{iX_{1}∩X_{2}} ⊕_{2} K_{iX_{1}∩Y_{2}} ⊕_{2} K_{iY_{1}∩X_{2}} ⊕_{2} K_{iY_{1}∩Y_{2}},

for every i ∈ {1, 2, 3, 4} — when |Z| = 1, we take K_{iZ} as the empty matroid and set e_{Z} equal to the element belonging to Z. Observe that the 2-separations {X_{1}, Y_{1}} and {X_{2}, Y_{2}} induce 2-separations on J_{i}. Thus, J_{i} is a circuit or cocircuit, for every i ∈ {1, 2, 3, 4}.

For every i ∈ {1, 2, 3, 4}, J_{i} = H_{i} ⊕ L_{i}, where H_{i} and L_{i} are matroids such that E(H_{i}) = {e_{1}, e_{X_{1}∩X_{2}}, e_{X_{1}∩Y_{2}}} and E(L_{i}) = {e_{1}, e_{Y_{1}∩X_{2}}, e_{Y_{1}∩Y_{2}}}. Observe that

N_{1} = H_{i} ⊕_{2} K_{iX_{1}∩X_{2}} ⊕_{2} K_{iX_{1}∩Y_{2}},

for every i ∈ {1, 2, 3, 4}. Thus,

K_{1X_{1}∩Z_{2}} = K_{2X_{1}∩Z_{2}} = K_{3X_{1}∩Z_{2}} = K_{4X_{1}∩Z_{2}},

for every Z ∈ {X, Y }, and H_{1} = H_{2} = H_{3} = H_{4}. From the last identity, we have that J_{1} = J_{2} = J_{3} = J_{4}. Similarly, we have that

K_{1Z_{1}∩X_{2}} = K_{2Z_{1}∩X_{2}} = K_{3Z_{1}∩X_{2}} = K_{4Z_{1}∩X_{2}},

for both Z ∈ {X, Y }. Hence M is equal to

(K_{1Y_{1}∩Y_{2}}, K_{2Y_{1}∩Y_{2}}, K_{3Y_{1}∩Y_{2}}, K_{4Y_{1}∩Y_{2}}) ⊕_{2} N,

where N = J_{i} ⊕_{2} K_{iX_{1}∩X_{2}} ⊕_{2} K_{iX_{1}∩Y_{2}} ⊕_{2} K_{iY_{1}∩X_{2}}, for every i ∈ {1, 2, 3, 4}. We arrive at a contradiction because X_{1} ∪ X_{2} cannot be a dead set.

By (2.6), we can decompose a non-trivial connected quad M as

M = H ⊕_{2} N_{1} ⊕_{2} N_{2} ⊕_{2} ⋯ ⊕_{2} N_{k},

where H is a non-trivial irreducible quad and, for i ∈ {1, 2, …, k}, N_{i} is a connected matroid such that E(N_{i}) ∩ E(H) = {e_{i}}, for e_{i} ∉ E(M), E(N_{i}) ∩ E(N_{j}) = ∅ and e_{i} ≠ e_{j}, for every i ≠ j. As this decomposition is unique, up to the labels of the base points of the 2-sums, by (2.6), we say that H is the core of M and that N_{1}, N_{2}, …, N_{k} are the leaves of M. We refer to it as the canonical decomposition for M. We shall associate the following function with M:

γ(M) = ⋃_{i=1}^{k} E(N_{i}) \ {e_{i}}.

Observe that γ(M) = ∅, when M is irreducible.

During the rest of this section, we shall study the deletion and contraction of elements belonging to a non-trivial irreducible quad. First, we shall give some definitions. For an element e of a non-trivial irreducible quad M, we define del(e) as the number of leaves of M\e, when M\e is non-trivial, and as ∞ otherwise. Similarly, we define con(e) as the number of leaves of M/e, when M/e is non-trivial, and as ∞ otherwise. We also set

del(M) = min{del(e) : e ∈ E(M)} and con(M) = min{con(e) : e ∈ E(M)}.

When del(M) = con(M) = ∞, we say that M is an almost trivial quad. Now, we shall present the characterization of the almost trivial quads. To do this, we need to set more notation: when C_{1}, C_{2}, …, C_{n} are different circuit-hyperplanes of a matroid M, we denote by M_{C_{1},C_{2},...,C_{n}} the matroid obtained from M after the relaxation of all the circuit-hyperplanes C_{1}, C_{2}, …, C_{n}.

Now, we need the following corollary of a result of Mills, that appears in [5]:

(2.7) Let M and N be different matroids both loopless and coloopless defined in the same ground set. If, for every e ∈ E(M), M\e = N\e or M/e = N/e, then one of M and N is a relaxation of the other.

(2.8) If M is almost-trivial, then there is a matroid M having a pair of circuit-hyperplanes X and Y such that {X, Y } is a partition of E(M) and M ≡ (M_{X,Y} , M, M_{Y} , M_{X}). This quad is denoted by Q(M, X, Y).

Proof: By hypothesis, for every e ∈ E(M), we have that

{M_{1}\e, M_{2}\e} = {M_{3}\e, M_{4}\e} and {M_{1}/e, M_{2}/e} = {M_{3}/e, M_{4}/e}.

For i ∈ {1, 2} and j ∈ {3, 4}, when M_{i}\e = M_{j}\e, then M_{i}/e = M_{7−j}/e, otherwise M_{i}/e = M_{j}/e and hence M_{i} = M_{j} and M is trivial, a contradiction. Thus, there is a partition {X, Y } of E(M) such that

M_{1}\x = M_{3}\x, M_{1}/x = M_{4}/x, M_{1}/y = M_{3}/y and M_{1}\y = M_{4}\y,

for every x ∈ X and y ∈ Y.

We denote by C_{ij} the set C(M_{i}) △ C(M_{j}). By (1.2) and (2.7), we have that

C_{13} = C_{24} = {X} ∪ {X ∪ {y} : y ∈ Y } and
C_{14} = C_{23} = {Y } ∪ {Y ∪ {x} : x ∈ X}.

To conclude the proof of this lemma, we observe that there is an i ∈ {1, 2, 3, 4}, say i = 2, such that X and Y are both circuit-hyperplanes of M_{2}, which is taken to be M. Thus, M_{1} = M_{X,Y}. Note that both X and Y cannot be a circuit of M_{j}, for j ∈ {3, 4}, otherwise M_{2} = M_{j} and M is trivial. Hence, by (1.2), we may suppose that X is a circuit of M_{3} and Y is a circuit of M_{4}. So, M_{3} = M_{Y} and M_{4} = M_{X}.

(2.9) If M is a non-trivial connected quad, then M has an almost-trivial quad as a minor.

Proof: Suppose that this corollary is not true. Let M be a minimal counterexample for it. Observe that M is irreducible, otherwise, by the choice of M, the core N of M has an almost-trivial quad as a minor which must be a minor of M as well. By its choice, M is not almost-trivial, and there is an element e of E(M) such that M\e or M/e is non-trivial, say M\e. As M\e is connected because M is irreducible, it follows that M\e has an almost-trivial quad as a minor. We arrive at a contradiction.

We say that a quad M is binary, when, for every i ∈ {1, 2, 3, 4}, M_{i} is a binary matroid.

(2.10) There exists no non-trivial connected binary quad.

Proof: By (2.9), every non-trivial connected binary quad must have an almosttrivial quad N as a minor. Thus, N must be binary. By (2.8), N ≡ Q(N; X, Y), for some matroid N. As N_{X} is a binary matroid, it follows that |X| = |Y | = 2, otherwise N_{X}\Y′/X′ is isomorphic to U_{2,4}, for some X′ ⊂ X and Y′ ⊂ Y such that |X′| = |Y′| = r(N) − 2. Thus, N = N|X ⊕ N|Y and N_{X,Y} must be isomorphic to U_{2,4}. So, N cannot exist and the result follows.

Seymour’s theorem that was stated in the introduction is a consequence of this result, since (M, M^{∗}, N, N^{∗}) must be a non-trivial binary connected quad, when M and N are connected binary matroids having the same connectivity function such that M ≠ N and M ≠ N^{∗}.

We say that a quad M is semi-binary, when M_{1} and M_{2} are binary matroids or M_{3} and M_{4} are binary matroids. Thus, the proof of (2.10) can be easily adapted to prove the following result:

(2.11) A semi-binary almost-trivial quad has four elements.

Our goal is to construct all the semi-binary irreducible non-trivial quads, to conclude that they cannot be equivalent to the core of (M, M^{∗}, N, N^{∗}), for a connected binary matroid M having the same connectivity function as N. This shall be done in the last section of this paper.

Now, we shall prove a result that is not needed in this paper, but is fundamental to study the uniqueness of the decomposition of the rank function of a 2-polimatroid as the sum of rank functions of matroids. We shall state and prove it here for future reference.

(2.12) If M is a non-trivial connected quad, then there is at most one i ∈ {1, 2, 3, 4} such that M_{i} is not connected. Moreover, if M_{i} is not connected, then it has two connected components.

Proof: Suppose that this result is not true and choose a minimal counterexample M. Clearly M is irreducible. By (2.8), M cannot be an almost-trivial quad. So, M has an element e such that M\e or M/e is non-trivial, say M\e. As M is irreducible, it follows that M\e is connected. Thus, by the choice of M, there is at most one i such that M_{i}\e is not connected. So, e must be a loop or coloop of some M_{j}, for j ≠ i. But this is contrary to (2.2).

3 A splitter-type theorem for quads

In this section, we shall prove a splitter-type theorem for irreducible quads. It says that it is possible to get a non-trivial irreducible quad from an almosttrivial quad or a wheel-whirl quad, which is going to be defined below, by a sequence of one elements lifts or extensions without leaving the class of irreducible quads. This theorem plays a central hole in the construction of all semi-binary irreducible quads, since permits an inductive proof.

Let N be a matroid having a circuit-hyperplane C and let U be a disconnected matroid defined on the same ground set as N such that U|C ≃ U_{|C|−1,|C|} and U|(E(N) \ C) ≃ U_{1,|E(N)\C|}. By (1.2), (N, U_{C}, N_{C}, U) is a quad, which is denoted by Q(N; C). When N ≃ M(W_{n}), for n ≥ 2, Q(N; C) is denoted by W_{n} and is called the wheel-whirl quad of rank n. Now, we state the main result of this section.

(3.1) If M is a non-trivial irreducible quad, then

(i) there is e ∈ E(M) such that M\e is non-trivial and irreducible; or

(ii) there is e ∈ E(M) such that M/e is non-trivial and irreducible; or

(iii) M is an almost-trivial quad; or

(iv) M is a wheel-whirl quad.

Before the proof of (3.1), we shall give the definition of a chain of triangles and triads of a matroid with a small modification from the one which appears in Oxley [8]: for a matroid M and integer m ≥ 4, the sequence z_{1}, z_{2}, …, z_{m}, z_{m+1}, z_{m+2} of elements of M is an admissible sequence of M, when (i) z_{1}, z_{2}, …, z_{m} are all distinct; (ii) for i ∈ {1, 2, …, m}, Z_{i} = {z_{i}, z_{i+1}, z_{i+2}} is a triangle when i is odd and a triad when i is even. We have the following theorem:

(3.2) Suppose that z_{1}, z_{2}, …, z_{m}, z_{m+1}, z_{m+2} is an admissible sequence of a matroid M.

(i) (6.1 of Seymour [10]) When M is connected, z_{m+1} = z_{1} and z_{m+2} = z_{2}, then m = 2n and M is isomorphic to W_{n} or M(W_{n}).

(ii) (see Tutte [12] or Oxley and Reid [9]) When M is 3-connected and z_{m+2} = z_{1}, then m = 2n − 1 and M is isomorphic to a W_{n} or M(W_{n}).

We say that Z_{1}, Z_{2}, …, Z_{m} is a chain of M. This chain is said to be closed, when Z_{1} ∩ Z_{m} ≠ ∅. In this case, we have (i) or (ii) of (3.2).

Proof of (3.1): We may suppose that 0 < min{del(M), con(M)} < ∞, otherwise the result follows: (a) when del(M) = 0, we have (i); (b) when con(M) = 0, we have (ii); (c) when del(M) = con(M) = ∞, then M is almost-trivial and we have (iii).

As the classes of almost-trivial quads and wheel-whirl quads are both closed under duality, we can replace M by M^{∗}, when necessary, and we may suppose that

γ = min_{e∈E(M)}{|γ(M\e)| : del(e) < ∞} ≤ min_{e∈E(M)}{|γ(M/e)| : con(e) < ∞}.

Choose an element e belonging to {f ∈ E(M) : γ = |γ(M\f)|} such that del(e) is maximum. So, for k = del(e),

M\e = H ⊕_{2} N_{1} ⊕_{2} N_{2} ⊕_{2} ⋯ ⊕_{2} N_{k},

where H is a non-trivial and irreducible quad and N_{i} is a connected matroid, for each i ∈ {1, 2, …, k}. Moreover, let e_{i} be the element belonging to both E(H) and E(N_{i}), for every i ∈ {1, 2, …, k}. We also set E_{i} = E(N_{i}) \ {e_{i}}, for every i ∈ {1, 2 …, k}.

(3.3) For every i ∈ {1, 2, …, k} and f ∈ E_{i}, N_{i}\f is not connected.

Suppose that N_{i}\f is connected, for some f ∈ E_{i} and i ∈ {1, 2, …, k}, say i = k. So,

M\{e, f} = H ⊕_{2} N_{1} ⊕_{2} N_{2} ⊕_{2} ⋯ ⊕_{2} N_{k−1} ⊕_{2} N_{k}\f

is the canonical decomposition of M\{e, f}. Hence M\{e, f} is non-trivial and connected. Thus, M\f is also non-trivial and connected.

By the decomposition of M\{e, f}, we have that: if {X, Y } is a 2-separation for M\{e, f}, then X ⊂ E_{k} or Y ⊂ E_{k} or E_{k} \ {f} ⊆ X or E_{k} \ {f} ⊆ Y.

In this paragraph, we shall prove that the dead sets of M\f are contained in (E_{k} \{f})∪{e}. Suppose that {X ∪{e}, Y } is a 2-separation for M\f. First, we shall prove that |X| ≥ 2. Suppose that |X| = 1, say X = {x}. By (2.5), we have two cases to deal with: (a) {e, x} is contained in a parallel class of M_{i}\f, for every i ∈ {1, 2, 3, 4}. In this case, we arrive at a contradiction, because {{e, x}, E(M) \ {e, x}} is a 2-separation for M; or (b) {e, x} is contained in a series class of M_{i}\f, for every i ∈ {1, 2, 3, 4}. Hence, x is a coloop of M_{i}\{e, f} and we arrive at a contradiction, since M\{e, f} is connected. Thus, |X| ≥ 2 and {X, Y } is a 2-separation for M\{e, f}. Note that E_{k} \ {f} ⊈ Y, otherwise {X ∪ {e}, Y ∪ {f}} is a 2-separation for M because E_{k} \ {f} spans f in M_{i}, for every i ∈ {1, 2, 3, 4}. Similarly, we have that E_{k} \ {f} ⊈ X. So, X ⊂ E_{k} or Y ⊂ E_{k}, by the previous paragraph. Hence the dead set of this 2-separation must be contained in (E_{k} \ {f}) ∪ {e}.

So, by the choice of e,

|γ(M\e)| ≤ |γ(M\f)| ≤ |E_{k}| = |γ(M\e)| − ∑_{i=1}^{k−1} |E_{i}|.

Thus, k = 1 and |γ(M\e)| = |γ(M\f)|. Hence, by the choice of e, M\f has just one leave, which must have as its ground set Z = (E_{1} \ {f}) ∪ {e}. We arrive at a contradiction because {Z, E(M) \ (Z ∪ {f})} is a 2-separation for M \ f and Z spans f in M_{i}, for every i ∈ {1, 2, 3, 4}.

(3.4) For every i ∈ {1, 2, 3, 4} and j ∈ {1, 2, …, k}, cl_{M_{i}}(E(M) \ (E_{j} ∪ {e})) ∩ E_{j} = ∅

If f ∈ cl_{M_{i}}(E(M) \ (E_{j} ∪ {e})) ∩ E_{j}, then f must be in parallel with e_{j} in N_{j} and hence N_{j}\f is connected, which is contrary to (3.3).

(3.5) k = 1 and |E_{1}| = 2.

Without loss of generality, we may suppose that

|E_{1}| ≤ |E_{2}| ≤ ⋯ ≤ |E_{k}|.

If f ∈ E(N_{k}) \ {e_{k}}, then, by (3.3), N_{k}/f is connected and the canonical decomposition of M\e/f is the following

M\e/f = H ⊕_{2} N_{1} ⊕_{2} N_{2} ⊕_{2} ⋯ ⊕_{2} N_{k−1} ⊕_{2} N_{k}/f.

Now, we shall study the maximal dead sets of M/f. Suppose that {X ∪ {e}, Y } is a 2-separation for M/f. We shall prove that its dead set is equal to: (a) X ∪ {e} and |X| = 1; or (b) X ∪ {e} and X ⊆ E_{i} \ {f}, for some i ∈ {1, 2, …, k}.

If |X| = 1, then X ∪ {e} is its dead set. Thus, we may suppose that |X| ≥ 2. So, {X, Y } is a 2-separation for M\e/f. Now, we have two cases to deal with:

(c) Y ⊆ E_{i} \ {f}, for some i ∈ {1, 2, …, k} or (d) X ⊆ E_{i} \ {f}, for some i ∈ {1, 2, …, k}. When (d) happens, we have (b). So, we may suppose that (c) happens. Thus, Y must span f in N_{i}, for some i ∈ {1, 2, 3, 4}, otherwise {X ∪ {e, f}, Y } is a 2-separation for M. By (3.4), this cannot happens when i < k. So, i = k and let C be a circuit of N_{k} such that f ∈ C ⊆ Y ∪ {f}. As N_{k}\g is not connected, for every g ∈ C, by (3.3), it follows that C \{f} contains a 2-cocircuit D of N_{k}, by a result of Oxley (lemma 10.2.1 of [7]). Observe that D is a 2-cocircuit of M_{i}/f, for every i ∈ {1, 2, 3, 4}, since X spans e in M_{i}/f.

Hence D is a 2-cocircuit of M_{i}, for every i ∈ {1, 2, 3, 4}, and we arrive at a contradiction.

By (2.6), the maximal dead sets are disjoint. So, M/f has just one dead set. Hence

2(k − 1) + |E_{k}| ≤ ∑_{i=1}^{k} |E_{i}| = |γ(M\e)| ≤ |γ(M\f)| ≤ |E_{k}| + 1.

Thus, k = 1.

Now, we shall prove that |γ(M\e)| = 2. When |γ(M\e)| > 2, we must have |E_{1}| > 2 and (E_{1} \ {f}) ∪ {e} as a dead set of M/f, otherwise {e, x} is a dead set for M/f and we arrive at a contradiction by the choice of e. As {(E_{1} \ {f}) ∪ {e}, E(M) \ (E_{1} ∪ {e})} cannot be a 2-separation for M/f, since E(M) \ (E_{1} ∪ {e}) does not span f in M_{l}, for every l ∈ {1, 2, 3, 4}, by (3.4), we arrive at a contradiction and |E_{1}| = 2.

Consider the following two sets:

Z = {e ∈ E(M) : |γ(M\e)| = 2} and W = {e ∈ E(M) : |γ(M/e)| = 2}.

By (3.5), Z ∪ W ≠ ∅. Thus, for each e ∈ Z and f ∈ W, we have that

M\e = H_{e} ⊕_{2} N_{e} and M/f = H_{f} ⊕_{2} N_{f},

where H_{e} and H_{f} are non-trivial irreducible quads and N_{e} is a matroid isomorphic to U_{2,3} and N_{f} is a matroid isomorphic to U_{1,3}. We set W_{e} = E(M)∩E(N_{e}) and Z_{f} = E(M) ∩ E(N_{f}). Observe that W_{e} ⊆ W, Z_{f} ⊆ Z and |W_{e}| = |Z_{f}| = 2. Moreover,

(3.6) For each i ∈ {1, 2, 3, 4}, e ∈ Z and f ∈ W, W_{e} or W_{e} ∪ {e} is a cocircuit of M_{i} and Z_{f} or Z_{f} ∪ {f} is a circuit of M_{i}.

(3.7) f ∈ W_{e} if and only if e ∈ Z_{f}.

(3.8) When W_{e} ∪ {e} is a triad of M_{i}, for e ∈ Z and i ∈ {1, 2, 3, 4}, then Z_{f_{1}} ∪ {f_{1}}, W_{e} ∪ {e}, Z_{f_{2}} ∪ {f_{2}} is a chain of M_{i}, where W_{e} = {f_{1}, f_{2}}.

First, we shall prove that Z_{f} ∪ {f} is a triangle of M_{i}, for every f ∈ W_{e}. When Z_{f} ∪ {f} is not a triangle of M_{i}, then Z_{f} is a circuit of M_{i}, by (3.6). Observe that e ∈ Z_{f} ∩ (W_{e} ∪ {e}), by (3.7). Thus, by orthogonality, we have that Z_{f} = {e, g}, where g ∈ W_{e} \ {f}. As {e} is a loop of M_{i}/g and M/g is connected, by (2.2), it follows that M/g is trivial, a contradiction. Hence Z_{f} ∪ {f} is a triangle of M_{i}.

Now, we shall prove that |(Z_{f} ∪{f})∩(W_{e}∪{e})| = 2. When X = Z_{f} ∪{f} = W_{e}∪{e}, it follows that {X, E(M)\X} is a 2-separation for M_{i}. As g ∈ Z_{f} ∩W_{e}, it follows that X is a triad of M_{j}, for every j ∈ {1, 2, 3, 4}, otherwise, by (3.6), W_{e} is a cocircuit of M_{j}, for some j ∈ {1, 2, 3, 4}, and f is a coloop of M_{j}\g, which is contrary to the fact that M\g is non-trivial and connected, by (2.2). Similarly, we have that X is a triangle of every M_{j}, for every j ∈ {1, 2, 3, 4}. Hence {X, E(M) \ X} is a 2-separation for M.

Now, we shall state the dual of this result:

(3.9) When Z_{f} ∪ {f} is a triangle of M_{i}, for f ∈ W and i ∈ {1, 2, 3, 4}, then W_{e_{1}} ∪ {e_{1}}, Z_{f} ∪ {f}, W_{e_{2}} ∪ {e_{2}} is a chain of M_{i}, where Z_{f} = {e_{1}, e_{2}}.

By (3.5) and (3.6), for some e ∈ E(M), it follows that W_{e} ∪ {e} is a triad of M_{1} or M_{2}, say M_{1}, since M is irreducible. By (1.2), it must be a triad of M_{3} or M_{4}, say M_{3}. Thus, by (3.8) and (3.9), this triad is contained in a chain C of both M_{1} and M_{3} which must close as in (i) of (3.2). Let R be the set of elements of E(M) belonging to two triangles of C and let S be the set of elements of E(M) belonging to two triads of C. We define X = R ∪ S. Thus, by (3.2)(i), {X, E(M) \ X} is a 1-separation for both M_{1} and M_{3} and M_{1}|X and M_{3}|X are equal to a wheel or a whirl having rim R ⊆ Z and set of spokes S ⊆ W. Thus, one is a whirl and the other to a wheel, otherwise M is trivial, by (2.3). As M_{2}|X and M_{4}|X cannot be connected components of M_{2} and M_{4}, respectively, equal to the same wheel or whirl, by (2.3), it follows that C is not a chain for both M_{2} and M_{4} and W_{e} and Z_{f} is a cocircuit and a circuit, respectively, for every e ∈ S and f ∈ R, by (3.6). As S is a circuit of M_{2} or M_{4}, by (1.2), it follows that S is circuit which is a connected component of one of these matroids, since S is contained in one of its series classes. Similarly, R is a cocircuit which is a connected component of M_{2} or M_{4}. As M|X is a non-trivial connected quad, it follows that r_{M_{l}}(X) = r(M|X) is independent of l. So, R and S are connected components of the same matroid M_{i}, for i ∈ {2, 4}, since S is a basis for X in the other. Thus, {X, E(M) \ X} is a 1-separation for M. and it follows that X = E(M). We have (iv) of theorem 1.

4 Irreducible semi-binary quads

The main result of this section gives a description of all the semi-binary irreducible quads and from it we derive theorem 2. We need the following lemma which is similar to ones of Lemos [3] or Oxley [6]:

(4.1) Let N be a matroid having a circuit-hyperplane C without parallel elements.

(i) If {X, Y } is a 1-separation for N, then {X, Y } = {C, E(N) \ C}.

(ii) If {X, Y } is a 2-separation for N, then {X, Y } = {C, E(N) \ C} or Z ⊂ C

is contained in a series class of N, for some Z ∈ {X, Y }.

(iii) If |C| ≥ 3 and N is binary and not 3-connected, then C contains a nontrivial series class of N.

Proof: (i) Observe that {X, Y } = {C, E(N) \ C} because C is a circuit of N and E(N) \ C is a cocircuit of N.

(ii) For Z ∈ {X, Y }, we have that

r(Z) ≥ min{|C| − 1, |Z ∩ C|} + min{1, |Z \ C|}.

When C ∩ Z ≠ ∅, for both Z ∈ {X, Y }, we have that

|C| + 1 = r(N) + 1 = r(X) + r(Y) ≥ |C| + min{1, |X \ C|} + min{1, |Y \ C|}.

So, Z \ C = ∅, for some Z ∈ {X, Y } and the result follows. When C ∩ Z = ∅, for some Z ∈ {X, Y }, say Z = X, we have that Z = C, otherwise r(Y) = r(N) and X is a parallel class of N.

(iii) From (i) and (ii), we have (iii) unless {C, E(N)\C} is the only 2-separation for N and it is exact. In this case, we can write N = N_{1} ⊕_{2} N_{2}, where N_{1} and N_{2} are binary matroids such that E(N_{2}) = C ∪ {e}, for a new element e. As r^{∗}(N_{2}) = 2 and |E(N_{2})| = |C|+1 ≥ 4, it follows that N_{2} has a non-trivial series class which must be contained in C.

(4.2) M is a non-trivial semi-binary irreducible quad if and only if there is a 3-connected binary matroid N having a circuit-hyperplane C such that M ≡ Q(N; C) or M ≃ W_{2}.

Proof: We shall prove the “only if” part of the theorem, since the “if” is trivial. Suppose that it is not true and choose a counter-example M which is minimal. By (2.11), an almost-trivial matroid cannot be semi-binary, unless it is isomorphic to W_{2}. So, by (3.1), (i) M is isomorphic to a wheel-whirl quad. In this case, we may take N equal to the wheel and C to be its rim and the result follows; or (ii) M has an element e such that M\e or M/e is irreducible. As this theorem is invariant under duality, we may suppose that M has an element e such that M\e is irreducible. So, by the choice of M, M\e ≡ Q(N; C), for a binary 3-connected matroid N, or M\e ≃ W_{2}. When the first possibility occurs, we suppose that M_{1}\e = N and M_{3}\e = N_{C}. We divide the proof of this theorem in some lemmas. At the end, we shall arrive at a contradiction.

(4.3) M\e ≡ Q(N; C) and min{r(N), r(N^{∗})} ≥ 3.

By the next lemma, up to isomorphism, there is just one non-trivial semibinary irreducible quad having rank equal to 2: W_{2}. So, M\e cannot be isomorphic to it, otherwise, by (4.4), M must also be isomorphic to W_{2}. Thus, M\e ≡ Q(N; C) and both r(N) and r(N^{∗}) are at least three.

(4.4) If H is a non-trivial semi-binary irreducible quad such that r(H) = 2, then H ≃ W_{2}.

Proof: It is enough to prove that W_{2} does not have an irreducible semibinary extension. So, suppose that H\e is isomorphic to W_{2} and that E(H) = {a, b, c, d, e}. By (1.2), we may suppose that {a, b} and {c, d} are circuits of H_{2}, {a, b} is a circuit of H_{3} and {c, d} is a circuit of H_{4}. As H_{3} and H_{4} do not have a minor isomorphic to U_{2,4}, since H is semi-binary, it follows that {e, e_{i}} is a circuit of H_{i}, for i ∈ {3, 4}. Observe that e_{3} ≠ e_{4}, otherwise {{e, e_{3}}, E(H) \ {e, e_{3}}} is a 2-separation for H, by (1.2). Thus, by (1.2), {e, e_{3}} or {e, e_{4}} is a circuit of H_{2}, otherwise {e_{3}, e_{4}} is a circuit of H_{1}. So, H_{2} has a parallel class P with three elements. P must be a parallel class of H_{3} or H_{4} because H/e is connected and trivial, since it has loops, by (2.2). So, H_{2}/e = H_{i}/e, for some i ∈ {3, 4}, and P is a parallel class of M_{i}. This cannot occurs, since e_{3} ∈ {a, b} if and only if e_{4} ∈ {c, d}. That is, both M_{3} and M_{4} have a three element parallel class or both does not have it.

(4.5) C does not span e in M_{1}.

Suppose that C spans e in M_{1}. Choose a circuit C′ of M_{i}, for i ∈ {1, 2}, such that e ∈ C′ ⊆ C ∪ {e} and |C′ ∩ C| is minimum. First, we shall prove that |C \ C′| ≥ 2. As M_{1} is binary and C spans e in M_{1}, there are circuits C_{1} and C_{2} of M_{1} such that C_{1} ∩ C_{2} = {e} and C_{1} △ C_{2} = C. We may suppose that |C_{1}| ≤ |C_{2}|. Thus, |C′| ≤ |C_{1}| and |C \ C′| ≥ |C \ C_{1}| = |C ∩ C_{2}| ≥ 2, since |C| ≥ 3, by (4.3).

In this paragraph, we prove that C′ is a circuit of M_{i}, for every i ∈ {1, 2, 3, 4}. Observe that M/(C′ ∩ C) is non-trivial, since |C \ C′| ≥ 2 and hence

M_{3}\e/(C′ ∩ C) = N_{C}/(C′ ∩ C) = [N_{E(N)\C}^{∗}\(C′ ∩ C)]^{∗}

is non-binary. So, M/(C′ ∩ C) is not connected, by (2.2), because M_{i}/(C′ ∩ C) has a loop, for some i ∈ {1, 2}. By the dual of (4.1)(i), M_{1}\e/(C′ ∩ C) = N/(C′ ∩ C) is connected. So, the only 1-separation for M/(C′ ∩ C) has {e} as one of its sets. Thus, e is a loop of M_{i}/(C′ ∩ C), for every i ∈ {1, 2, 3, 4}, otherwise it would be a coloop of M_{i}, for some i ∈ {1, 2, 3, 4}, which is contrary to (2.2). Thus, by (1.2), C′ is a circuit of M_{i}, for every i ∈ {1, 2, 3, 4}.

Observe that |C′| ≥ 3, otherwise C′ is a parallel class of M_{i}, for every i ∈ {1, 2, 3, 4} and M is not irreducible. Now, C′′ = (C \ C′) ∪ {e} is a circuit of M_{1}. Similarly to the previous paragraph, we have that M/(C′′ ∩ C) is a non-trivial quad, since |C \ C′′| = |C ∩ C′| ≥ 2 and M_{3}/(C′′ ∩ C) has U_{2,4} as a minor. Observe that the only 1-separation for M_{1}/(C′′ ∩ C) has {e} as one of its sets, by the dual of (4.1)(i) applied to N/(C′′ ∩ C) = M_{1}/(C′′ ∩ C)\e. But M_{2}/(C′′ ∩ C) does not have a 1-separation having {e} as one of its sets, because there is just one circuit of M_{2} contained in C ∪ {e}, namely C′. We arrive at a contradiction, by (2.2), since M/(C′′ ∩ C) is a non-trivial connected quad having a matroid with a loop.

(4.6) M_{1} is a 3-connected matroid.

By (2.2), it is enough to prove that {e, f} is not a circuit of M_{1} for every f ∈ E(M) \ {e}. Suppose that {e, f} is a circuit of M_{1}. By (4.5), f ∉ C. By (1.2), we have two cases to consider: (i) {e, f} is a circuit of M_{3}; or (ii) {e, f} is a circuit of M_{4}. In both cases, we shall arrive at a contradiction proving that {e, f} is a circuit of M_{i}, for every i ∈ {1, 2, 3, 4}.

First, we shall prove that {e, f} cannot be a circuit of M_{4}. If {e, f} is a circuit of M_{4}, then E(M) \ C is a parallel class of M_{4}. As |E(M)\C| ≥ 3, by (4.3), we can choose different elements a and b of E(M) \ (C ∪ {e}). By (1.2), it follows that {e, a} or {e, b} is a circuit of M_{2}, otherwise {a, b} is a parallel class of M_{1}. Hence e is in parallel with f in M_{2}, since both a and b are parallel to f in this matroid. By (1.2), {e, f} is also a circuit of M_{3}. We arrive at a contradiction.

When {e, f} is a circuit of M_{3}, C ∪ {e} is also a circuit of M_{3}, since e and f are parallel in this matroid. As C ∪{e} is not a circuit of M_{1}, by (4.5), it follows that C ∪ {e} is a circuit of M_{2}, by (1.2). Hence (C ∪ {e}) △ (C ∪ {f}) = {e, f} is also a circuit of M_{2}, since M_{2} is binary. Again, we arrive at a contradiction using (1.2).

(4.7) For every element f ∈ E(M) \ (C ∪ {e}), there is a triad T_{f} of M_{1} such that f ∈ T_{f} and T_{f} \ {f} ⊆ C.

First, we shall prove that M_{1}\f is not 3-connected. When M_{1}\f is 3connected, it follows that M\f is an irreducible non-trivial semi-binary quad. Thus, by the choice of M, M ≡ Q(N′; C′), for some 3-connected binary matroid N′. So, C = C′. Hence C ∪ {e} is also a circuit of M_{3} and e is not spanned by M_{1}. That is, C is a circuit-hyperplane of M_{1} and M_{3} = (M_{1})_{C}. We arrive at a contradiction and M_{1}\f is not 3-connected.

Let {X ∪ {e}, Y } be a 2-separation for M_{1}\f. Now, we shall prove that |X| ≥ 2. If |X| = 1, say X = {x}, then {x, e} is a series class of M_{1}\f, by (4.6). So, {e, f, x} is a triad of M_{1} and M_{1}\e = N is not 3-connected, a contradiction. Hence |X| ≥ 2 and {X, Y } is a 2-separation for M_{1}\{e, f} = N\f. By (4.1)(iii), it follows that there is Z′ ⊆ Z ⊆ C, for some Z ∈ {X, Y }, such that |Z′| = 2 and Z′ is contained in a series class of M_{1}\{e, f} = N\f. As X spans e in M_{1}, it follows that Z = Y, by (4.5), and Y′ is contained in a series class of M\f. Thus, we can take T_{f} = {f} ∪ Y′.

(4.8) If g ∈ T_{f} ∩ C, for some f ∈ E(M) \ (C ∪ {e}), then there is a triangle T_{g} of M_{1} such that {f, g} ⊆ T_{g} and T_{g} ∩ C = {g}.

First, we shall prove that M_{1}/g is not 3-connected. If M_{1}/g is 3-connected, then M/g is a non-trivial quad because M_{1}\e/g ≠ M_{3}\e/g, by (4.3). So, M/g is an irreducible non-trivial semi-binary quad and, by the choice of M, M/g ≡ Q(N′, C′) for a 3-connected binary matroid N′. Thus, C′ = C \ {g} and C ∪{e} or (C \{g})∪{e} is a circuit of M_{3}. Hence C′′ = (C \{g})∪{e} is a circuit of M_{3}, otherwise M_{3} = (M_{1})_{C}. As C′′∩T_{f} = {g′}, where T_{f} ∩C = {g, g′}, it follows that T_{f} is not a triad of M_{3}. Now, we shall prove that T_{f} is a triad of M_{3}\e. Observe that T_{f} is a triad of M_{1}\e = N, since this matroid is 3-connected. Thus, by the dual of (1.2), T_{f} is a triad of M_{3}\e or M_{4}\e. As, by orthogonality, T_{f} cannot be a triad of M_{4}\e, it follows that T_{f} is a triad of M_{3}\e. Hence T_{f} ∪{e} is a cocircuit of M_{3}. So, T_{f} ∪ {e} is a cocircuit of M_{2}, by the dual of (1.2). We arrive at a contradiction, by orthogonality, because P = E(M) \ (C ∪ {e}) is contained in a parallel class of M_{2} and P ∩ (T_{f} ∪ {e}) = {f}. Thus, M_{1}/g is not 3-connected.

Let {X ∪ {e}, Y } be a 2-separation for M_{1}/g. When |X| = 1, say X = {x}, then {x, e} is a parallel class of M_{1}/g, by (4.6). So, we can take T_{g} = {e, g, x}, since M_{1} is 3-connected and x ∉ C, otherwise C spans e in M_{1}, which is contrary to (4.5). Hence, we may suppose that |X| ≥ 2. Thus, {X, Y } is a 2-separation for M_{1}\e/g = N/g. By the dual of (4.1)(iii), it follows that there is Z ∈ {X, Y } and Z′ ⊆ Z such that Z′ ∩ C = ∅, |Z′| = 2 and Z′ is contained in a parallel class of M_{1}\e/g = N/g. Thus, we can take T_{g} = {g} ∪ Z′.

By (4.7) and (4.8), we can construct a chain of M_{1} having its rim contained in C and spokes in E(M) \ C. This chain must close, since the only element of E(M) \ C which may not belong to a triad of M_{1} is e. It may happens that this chain starts and ends with triangles that contain e. But, by (4.6), M_{1} is 3-connected, and by (3.2)(ii), it follows that M_{1} must be a wheel or whirl. We arrived at the final contradiction.

Now, we shall prove the main result of this paper:

Proof of theorem 2: Suppose that theorem 2 fails. Choose a pair of matroids M and N which contradict it. Observe that M = (M, M^{∗}, N, N^{∗}) is a semi-binary non-trivial connected quad having only connected matroids as coordinates. Thus, the core N of M must be semi-binary. As N is irreducible, by (4.2), it must be equivalent to some Q(H; C), for a 3-connected binary matroid H or it is isomorphic to W_{2}. We arrive at a contradiction because these quads has exactly one matroid which is not connected as a coordinate.

5 Acknowledgements

The author would like to thank Professor James Oxley for some discussions on the topic of this paper and all the staff of the Department of Mathematics of Louisiana State University for their hospitality.

6 References

[1] M.Lemos, Matroids having the same connectivity function, Discrete Mathematics 131 (1994), 153-161.

[2] M.Lemos, Non-binary matroids having at most three non-binary elements, Combinatorics, Probability and Computing 3 (1994), 355-369.

[3] M.Lemos e S.Mota, The reconstruction of a matroid from its connectivity function, in preparation.

[4] A.D.Mills, A matroid reconstruction result, Combinatorics, Probability and Computing 3 (1994), 371-373.

[5] U.S.R.Murty and I.Simon, A β-function that is not a sum of rank functions of matroids, Problèmes Combinatoiries et Théorie des Graphes (eds. J.- C.Bermond, J.-C.Fournier, M. Las Vergnas and D. Sotteau), Editions du CNRS, Paris, 1978, 305-306.

[6] J.Oxley, A characterization of a class of non-binary matroids, Journal of Combinatorial Theory Series B 49 (1990), 181-189.

[7] J.Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.

[8] J.Oxley, Structure theory and connectivity for matroids, Matroid Theory (eds. J.E.Bonin, J.Oxley and B.Servatius), Contemporary Mathematics 197 (1996), 129-170.

[9] J.Oxley and T.J.Reid, The smallest rounded sets of binary matroids, European Journal of Combinatorics 11 (1990), 47-56.

[10] P.D.Seymour, Decomposition of regular matroids, Journal of Combinatorial Theory Series B 28 (1980), 305-359.

[11] P.D.Seymour, On the connectivity function of a matroid, Journal of Combinatorial Theory Series B 45 (1988), 25-30.

[12] W.T.Tutte, Connectivity in matroids, Canadian Journal of Mathematics 18 (1966), 1301-1324.