ON SIZE, CIRCUMFERENCE AND CIRCUIT REMOVAL IN 3–CONNECTED MATROIDS

MANOEL LEMOS AND JAMES OXLEY

Abstract. This paper proves several extremal results for 3-connected matroids: a 3-connected matroid M of rank at least six has circumference c(M) at least six and, provided |E(M)| ≥ 4r(M) − 5, has a circuit whose deletion leaves a 3-connected matroid; if M has a basis B such that M\e is not 3connected for all e in E(M) − B, then |E(M)| ≤ 3r(M) − 4; and if M is minimally 3-connected but not hamiltonian, then |E(M)| ≤ 3r(M) − c(M).

1. Introduction

Let M be a matroid and A be a subset of E(M). Lemos and Oxley [7] and Lemos, Oxley, and Reid [8] considered the problem of finding a sharp upper bound on |E(M′) − A| where M′ is a 3-connected minor of M that is minimal with the property that M|A = M′|A. The following theorem, the main result of [7], solves this problem in the case when A spans M. Let λ_{1}(A, M) denote the number of connected components of M|A. Now M|A can be constructed from a collection Λ_{2}(A, M) of 3-connected matroids by using the operations of direct sum and 2-sum. It follows from work of Cunningham and Edmonds [1] that Λ_{2}(A, M) is unique up to isomorphism. We denote by λ_{2}(A, M) the number of matroids in Λ_{2}(A, M) that are not isomorphic to U_{1,3}, the three-element cocircuit.

1.1. Theorem. Let M be a 3–connected matroid other than U_{1,3} and let A be a non-empty spanning subset of E(M). If M has no proper 3–connected minor M′ such that M′|A = M|A, then

|E(M)| ≤ |A| + λ_{1}(A, M) + λ_{2}(A, M) − 2,

unless A is a circuit of size at least four, in which case,

|E(M)| ≤ 2|A| − 2.

It was also shown in [7] that, in a strong sense, the bound in this theorem is best-possible: given a simple matroid N having at least one circuit, there is a minor-minimal 3-connected matroid M for which M|E(N) = N such that |E(M)| attains the bound in the theorem. Therefore the theorem is best-possible for every restriction M|A for which r^{∗}(M|A) ≠ 0. The first new result of this paper sharpens Theorem 1.1 in the case that A is a basis of M.

1.2. Theorem. Let M be a 3-connected matroid of rank at least four and B be a basis of M. If M has no proper 3-connected minor that contains B and has B as a basis, then |E(M)| ≤ 3r(M) − 4.

1991 Mathematics Subject Classification. 05B35.

A minimally 3-connected matroid is a 3-connected matroid for which no singleelement deletion is 3-connected. Generalizing a result of Halin [3, Satz 7.6] for graphs, Oxley [10, Theorem 4.7] proved the following bound on the size of a minimally 3-connected matroid and characterized the matroids attaining equality in this bound.

1.3. Theorem. Let M be a minimally 3-connected matroid of rank at least three. Then

|E(M)| ≤ \{ \begin{matrix}2r(M), & if r(M) ≤ 6; \\ 3r(M) − 6, & if r(M) ≥ 7. \end{matrix}

Our second theorem uses Theorem 1.1 to derive a new bound on the size of a minimally 3-connected matroid. The circumference c(M) of a matroid that is not free is the maximum size of a circuit of M.

1.4. Theorem. Let M be a minimally 3-connected matroid. Then

|E(M)| ≤ \{ \begin{matrix}2r(M), & if M has a hamiltonian circuit; \\ 3r(M) − c(M), & otherwise. \end{matrix}

A comparison of the last two results prompts one to seek a lower bound on the circumference of a 3-connected matroid. The following such bound is obtained in Section 3, and an immediate consequence of this bound is that Theorem 1.4 sharpens Theorem 1.3.

1.5. Theorem. For a 3-connected matroid M of rank at least six, c(M) ≥ 6.

Mader [9] showed that every k-connected simple graph G with minimum degree at least k + 2 has a cycle C such that G\C, the graph obtained from G by deleting the edges of C, is k-connected. Jackson [4] extended this result for 2-connected graphs. In [5], Lemos and Oxley proved that if M is a 2-connected matroid for which

|E(M)| ≥ 2r(M) + 2 + max{0, 1 + r(M) − c(M)},

then M must have a circuit C such that M\C is 2-connected. Moreover, if |E(M)| ≥ 3r(M), they showed that this circuit can be chosen so as to avoid some arbitrarily chosen basis B of M. In Section 4, we prove the corresponding results in the 3-connected case:

1.6. Theorem. Let M be a 3-connected matroid such that r(M) ≥ 6. If

|E(M)| ≥ 3r(M) + 1 + max{0, r(M) − c(M)},

then M has a circuit C such that M\C is 3-connected.

1.7. Theorem. Suppose that M is a 3-connected matroid such that r(M) ≥ 4 and let B be a basis of M. If

|E(M)| ≥ 4r(M) − 3,

then M has a circuit C such that M\C is 3-connected and C ∩ B = ∅.

The terminology used here will follow Oxley [11].

2. A bound to the size of a minimally 3-connected matroid

In this section, we shall prove Theorems 1.2 and 1.4, a best-possible bound on the size of a minimal 3-connected matroid that maintains a fixed set as a basis, and a new bound on the size of a minimally 3-connected matroid as a function of its rank and circumference. Both of these results are consequences of Theorem 1.1. For a 3-connected matroid M and a subset A of its ground set, (M, A) is called a minimal pair if M has no 3-connected minor M′ for which M′|A = M|A.

The following lemma plays a key role in the proofs of both theorems. For a basis B of a matroid M and an element e of E(M) − B, the unique circuit of M that is contained in B ∪ e is denoted by C(e, B).

2.1. Lemma. Suppose that (M, B ∪ e) is a minimal pair and that r(M) ≠ 0. If B is a basis of M and e ∈ E(M) − B, then

|E(M)| ≤ \{ \begin{matrix}2r(M), & if C(e, B) is a hamiltonian circuit of M; \\ 3r(M) − |C(e, B)|, & otherwise. \end{matrix}

Proof. Suppose first that C(e, B) is a hamiltonian circuit of M. If r(M) ∈ {1, 2}, then E(M) = B ∪ e and the result holds. Thus we may assume that r(M) ≥ 3. Then, by applying Theorem 1.1 to the minimal pair (M, B ∪ e), we get that |E(M)| ≤ 2|C(e, B)| − 2 = 2r(M), and the result follows.

We may now suppose that C(e, B) is not a hamiltonian circuit of M. Observe that M|(B ∪ e) has C(e, B) as a connected component and B − C(e, B) as a nonempty set of coloops. Therefore

λ_{1}(B ∪ e, M) = 1 + |B − C(e, B)| = 1 + (|B| − |C(e, B)| + 1).

Thus λ_{1}(B ∪ e, M) = r(M) + 2 − |C(e, B)|. We also have that

λ_{2}(B ∪ e, M) = λ_{2}(C(e, B), M) + |B − C(e, B)|
= (|C(e, B)| − 2) + (|B| − |C(e, B)| + 1) = r(M) − 1.

Hence, by Theorem 1.1,

|E(M)| ≤ |B ∪ e| + λ_{1}(B ∪ e, M) + λ_{2}(B ∪ e, M) − 2
= (r(M) + 1) + (r(M) + 2 − |C(e, B)|) + (r(M) − 1) − 2
= 3r(M) − |C(e, B)|.

Theorem 1.4 is a straightforward consequence of this lemma.

Proof of Theorem 1.4. Let C be a circuit of M such that |C| = c(M). Choose an element e of C and a basis B of M such that C − e ⊆ B. Clearly C = C(e, B). The result follows immediately from Lemma 2.1. □

Lemos and Oxley [6] proved the analogue of the last theorem for minimally 2-connected matroids, namely, if M is a minimally 2-connected matroid, then

|E(M)| ≤ 2r(M) + 2 − c(M).

A matroid is hamiltonian if it has a spanning circuit. Evidently the circumference of such a matroid is one more than its rank. An interesting aspect of Theorem 1.4 is that the wheels and whirls are hamiltonian matroids that are extremal examples for the theorem. Moreover, for each r and each c such that 6 ≤ c ≤ r, we shall now describe an extremal example M for this theorem that has rank r and circumference c. Let {v_{1}, v_{2}, v_{3}} be one of the vertex classes in the bipartition of K_{3,r+3−c}. Let G be obtained from K_{3,r+3−c} as follows: add a path of length c − 4 to K_{3,r+3−c} that links v_{1} and v_{3} but is otherwise disjoint from K_{3,r+3−c}; then add a new edge joining v_{2} to every vertex of this path other than the ends. It is not difficult to check that the cycle matroid M of G has circumference c, rank r, and has 3r − c elements.

Next we shall prove Theorem 1.2 giving a best-possible upper bound on |E(M)| for a minimal pair (M, A) when A is a basis of M. In this theorem, observe that the bound on the rank of M in the hypothesis cannot be lowered: take M to be the rank-3 wheel and let B be its set of spokes. Then |E(M)| = 6, but 3r(M) − 4 = 5.

Proof of Theorem 1.2. First observe that (M, B ∪ e) is a minimal pair for all e in E(M)−B. Suppose that C(e, B) is hamiltonian for some e in E(M)−B. Then, by Lemma 2.1, |E(M)| ≤ 2r(M) and so, as r(M) ≥ 4, we have |E(M)| ≤ 3r(M) − 4. Thus we may assume that C(e, B) is non-hamiltonian for all e. In that case, by Lemma 2.1 again, |E(M)| ≤ 3r(M) − |C(e, B)| for all e. Hence we may assume that

|C(e, B)| = 3 for every element e of E(M) − B.  (1)

Next we shall prove that the theorem holds unless

C(e, B) ∩ C(f, B) ≠ ∅ whenever e ≠ f.  (2)

Suppose that e ≠ f and that C(e, B) ∩ C(f, B) = ∅. In this case, we shall consider the minimal pair (M, B∪{e, f}). Observe that M|(B∪{e, f}) has C(e, B), C(f, B), and each individual element of B −[C(e, B)∪C(f, B)] as its connected components. Thus, by (1),

λ_{1}(B ∪ {e, f}, M) = r(M) − 2 and λ_{2}(B ∪ {e, f}, M) = r(M) − 2.

Hence, by Theorem 1.1,

|E(M)| ≤ |B ∪ {e, f}| + (r(M) − 2) + (r(M) − 2) − 2 = 3r(M) − 4

and the result follows. Thus we may suppose that (2) holds.

Assume that there are distinct elements e, f, g in E(M) − B such that

C(e, B) = {e, a, b}, C(f, B) = {f, b, c}, C(g, B) = {g, c, a}.  (3)

In this case, we shall obtain a contradiction. We may assume that E(M) − (B ∪ {e, f, g}) contains an element h otherwise the theorem certainly holds. By (2), C(h, B) must intersect all of C(e, B), C(f, B), and C(g, B). Hence C(h, B) − h ⊆ {a, b, c}. Thus {a, b, c} spans E(M)−B. Moreover, B −{a, b, c} is non-empty since r(M) ≥ 4. Hence {B − {a, b, c}, (E(M) − B) ∪ {a, b, c}} is a 1-separation of the 3-connected matroid M; a contradiction. Thus (3) cannot occur.

We deduce that B has an element b such that b ∈ C(e, B) for every e in E(M)−B. Let b_{e} be the element of C(e, B) − {e, b}. If b_{e} = b_{f} for e ≠ f, then M|{b, b_{e}, e, f} is isomorphic to U_{2,4} and hence M\e is 3-connected; a contradiction. Thus b_{e} ≠ b_{f} whenever e ≠ f. Therefore

|E(M) − B| ≤ |B − b| = r(M) − 1

and the result follows. □

We now show that Theorem 1.2 is best-possible. Let K′′_{3,n} be the graph that is obtained from K_{3,n} by adding a new edge from one of the degree-n vertices of the latter to each of the other two degree-n vertices. Then equality is attained in the bound in Theorem 1.2 if we take M to be M(K′′_{3,n}) and B to be the set of edges meeting the vertex of degree n + 2 in K′′_{3,n}.

3. The circumference of a 3-connected matroid

For a k-connected graph G,the minimum vertex degree is at least k. When k ≥ 2, a well-known result of Dirac [2, Theorem 4] implies that the circumference of G is at least 2k provided that |V (G)| ≥ 2k. Moreover, this result is best-possible. Thus a 3-connected graph with at least six vertices has circumference at least six. In this section, we shall prove Theorem 1.5, a generalization of this result to 3-connected matroids having rank at least six.

Let L be a subset of the ground set of a matroid M and suppose that L is the union of a set of circuits of M and r^{∗}(M|L) = 2. Then L is what Tutte [12] has called a “line” of M. We shall call L a Tutte-line since the word “line” is also commonly used in matroid theory to mean a rank-2 flat. It is not difficult to see that every Tutte-line L of a matroid M has a canonical partition {L_{1}, L_{2}, …, L_{k}} such that a subset C of L is a circuit of M|L if and only if C = L − L_{i} for some i in {1, 2, …, k}. A Tutte-line L is connected if M|L is a connected matroid.

In the next proof, we shall make frequent use of the next two lemmas. Both parts of the first of these are elementary consequences of orthogonality, the property of a matroid that a circuit and a cocircuit cannot have exactly one common element. The second lemma was proved by Oxley [10, Theorem 2.5].

3.1. Lemma. (i) If C is a circuit of a 3-connected matroid and T_{1} and T_{2} are

distinct triads of M both of which meet C, then C ∩ T_{1} ≠ C ∩ T_{2}. (ii) If L is a Tutte-line of a matroid M and T is a triad of M, then T meets an

odd number of sets in the canonical partition of L.

3.2. Lemma. Let C be a circuit of a minimally 3-connected matroid M and suppose that |E(M)| ≥ 4. Then M has at least two distinct triads intersecting C.

Proof of Theorem 1.5. Let M be a counterexample to the theorem for which |E(M)| is minimal. Clearly M must be minimally 3-connected. Let C be a circuit of M such that |C| = c(M). Then 3 ≤ |C| ≤ 5.

Let D be the set of circuits D of M/C such that D is not a circuit of M and |D| ≥ 2.

3.3. Lemma. (i) |D| = 2 for every D in D; (ii) |C| ≥ 4; and (iii) for all D in D, the set C ∪ D is a connected Tutte-line of M having canonical

partition {X_{D}, Y_{D}, D} for some X_{D} and Y_{D} with |X_{D}|, |Y_{D}| in {2, 3}.

Proof. Suppose that D ∈ D. Then C ∪ D is a connected Tutte-line L of M. Let {L_{1}, L_{2}, …, L_{k}} be the canonical partition of L. As L is connected, k ≥ 3. Since (C ∪ D) − D is a circuit of M|L, we may assume, without loss of generality, that D = L_{1}. As L − L_{1} = C, a maximum-sized circuit of M, we must have that |L − L_{1}| ≥ |L − L_{i}| for all i. But |D| ≥ 2. Thus

2 ≤ |D| = |L_{1}| ≤ |L_{i}|  (4)

for all i. As ∪_{j=2}^{k}L_{j} = C and |C| ≤ 5, we deduce that k ≤ 3. Hence k = 3. Moreover, |L_{2}|, |L_{3}| ∈ {2, 3} and min{|L_{2}|, |L_{3}|} = 2. Thus, by (4), |D| = 2. In addition, |C| = |L_{2}| + |L_{3}| ≥ 4, and (iii) holds.

3.4. Lemma. c(M/C) ≤ 2.

Proof. Let C′ be a circuit of M/C with at least three elements. By Lemma 3.3, C′ ∉ D. Thus C′ is a circuit of M. Observe that M|(C ∪ C′) = (M|C) ⊕ (M|C′). Choose an element d of C′. Then M has a circuit C_{d} that contains d and meets C. Clearly C_{d} − C is a union of circuits of M/C. Take such a circuit D that contains d. Since D and C′ are both circuits of M/C, we cannot have that D = {d} otherwise D is a proper subset of C′. Hence |D| ≥ 2. Lemma 3.3 now implies that |D| = 2, say D = {d, d′}. Moreover, M|(C ∪ D) is connected. Since M|C′ is also connected, it follows that M|(C ∪ D ∪ C′), which equals M|(C ∪ C′ ∪ d′), is connected. Deleting d′ from the last matroid produces the disconnected matroid M|(C ∪ C′) with components M|C and M|C′. Thus M|(C ∪ C′ ∪ d′) is the series connection, with basepoint d′, of [M|(C ∪ C′ ∪ d′)]/C′ and [M|(C ∪ C′ ∪ d′)]/C. Now M|(C ∪ C′ ∪ d′) has a circuit D′ that contains d′ and at least two elements of C′, otherwise every element of C′ is parallel to d, a contradiction to the fact that C′ is a circuit of M of size at least three. Then D′ = D′_{1} ∪D′_{2} ∪d′ where D′_{1} ∪d′ and D′_{2} ∪ d′ are circuits of [M|(C ∪ C′ ∪ d′)]/C′ and [M|(C ∪ C′ ∪ d′)]/C, respectively. Hence D′ −C = D′_{2} ∪d′ and so D′ −C is a circuit of M/C that is not a circuit of M, and |D′ − C| ≥ 3. Thus D′ − C ∈ D yet Lemma 3.3 fails for it; a contradiction.

By Lemma 3.4, the connected components of M/C consist of loops and parallel classes. But each parallel class of M/C is a cocircuit of M and therefore has at least three elements. Let these rank-one components of M/C be H_{1}, H_{2}, …, H_{n}. Then n ≥ 1 since C does not span M. Therefore, as M is 3-connected and |E(M)− E(H_{i})| ≥ |C| ≥ 3, we have that

r(E(H_{i})) + r(E(M) − E(H_{i})) − r(M) ≥ 2.

Thus, as E(M) − E(H_{i}) is a hyperplane of M, it follows that

r(E(H_{i})) ≥ 3 for all i.  (5)

3.5. Lemma. C does not contain a triad of M.

Proof. Suppose that C contains a triad T of M. Choose a subset A of E(H_{1}) such that |A| = 2. Then A ∈ D so, by Lemma 3.3, C ∪ A is a connected Tutte-line of M having canonical partition {A, X, Y } with |X|, |Y | ∈ {2, 3}. Since X ∪ Y = C, it follows, by Lemma 3.1(ii), that {X, Y } = {T, C − T }. Hence, as |C| ≤ 5, we deduce that |C −T | ≤ 2. Thus |C −T | = 2 and |C| = 5. Moreover, for all 2-element subsets A of E(H_{1}), the set A ∪ (C − T) is a circuit C_{A} of M.

As M is minimally 3-connected, Lemma 3.2 implies that M has distinct triads T_{1} and T_{2} both of which meet C_{A}. By Lemma 3.1(i), T_{1} ∩ C_{A} ≠ T_{2} ∩ C_{A}. Thus, as |A| = 2, at least one of T_{1} and T_{2}, say the former, meets C − T. Now, by Lemma 3.1(ii), either (i) T_{1} ∩C ⊆ C −T; or (ii) T_{1} = {a, t, c} for some a in A, some t in T, and some c in C −T. Let A′ be a subset of E(H_{1})−a such that |A∩A′| = 1. Then C_{A′}, which equals A′ ∪ (C − T), cannot meet T_{1} in a single element, so (ii) does not hold. Hence (i) holds.

Let A′ be a subset of E(H_{1}) such that |A′∩A| = 1. By Lemma 3.1(ii), A′∩T_{1} = ∅, since {A′, T, C − T } is the canonical partition of A′ ∪ C. Let C − T = {x, y}. Then (C_{A} ∪ C_{A′}) − y, which equals A ∪ A′ ∪ x, contains a circuit of M. As |A ∪ A′| = 3 and (A ∪ A′ ∪ x) ∩ T_{1} = {x}, it follows that A ∪ A′ is a triangle of M. As A′ was an arbitrarily chosen subset of E(H_{1}) for which |A ∩ A′| = 1, we deduce that A spans E(H_{1}) in M. Hence r(E(H_{1})) = 2; a contradiction to (5).

3.6. Lemma. If i ∈ {1, 2, …, k} and {a, b} is a 2-element subset of E(H_{i}) that is contained in a triad of M, then E(H_{i}) is a triad of M.

Proof. Let T be a triad of M that contains {a, b} and suppose that T ∩ E(H_{i}) = {a, b}. By orthogonality, T ∩ C = ∅. Thus {a, b} is a union of cocircuits of M|(C ∪ E(H_{i})). But, since E(H_{i}) is a parallel class of M/C of size at least three, it follows that r(C ∪ E(H_{i})) = r(C) + 1 and E(H_{i}) is a cocircuit of M|(C ∪ E(H_{i})). This is a contradiction since {a, b} is a proper subset of E(H_{i}). We conclude that T ⊆ E(H_{i}). Since both T and E(H_{i}) are cocircuits of M, equality must hold here.

3.7. Lemma. For all i, the matroid M|(C ∪ E(H_{i})) has at most one 2-cocircuit contained in C.

Proof. Suppose that M|(C ∪ E(H_{i})) has at least two 2-cocircuits W_{1} and W_{2} contained in C. We now distinguish the following two cases: (i) |W_{1} ∩W_{2}| = 1; and (ii) |W_{1} ∩ W_{2}| = 0. In each case, we shall show that every 3-element subset of E(H_{i}) is a triangle so r(E(H_{i})) = 2; a contradiction to (5).

Assume that (i) holds. Then W_{1} ∪ W_{2} is contained in a series class of M|(C ∪ E(H_{i})). Let {a, b, c} be an arbitrary 3-element subset of E(H_{i}). Then Lemma 3.3 implies that, for each A in {{a, b}, {b, c}}, the set C ∪ A is a connected Tutte-line of M having canonical partition {A, X_{A}, Y_{A}} where each of X_{A} and Y_{A} has either two or three elements. Since both A ∪ X_{A} and A ∪ Y_{A} are circuits of M, we must have that W_{1} ∪ W_{2} is contained in and therefore equals X_{A} or Y_{A}. Thus both W_{1} ∪ W_{2} ∪ {a, b} and W_{1} ∪ W_{2} ∪ {b, c} are circuits of M. Hence if w ∈ W_{1}, then (W_{1} ∪ W_{2} ∪ {a, b, c}) − w contains a circuit C_{w} of M. As W_{1} ∪ W_{2} is contained in a series class of M|(C∪E(H_{i})) and w ∉ C_{w}, it follows that C_{w} avoids W_{1}∪W_{2}. Hence C_{w} is contained in and therefore equals {a, b, c}. It follows that r(E(H_{i})) = 2; a contradiction to (5).

We may now assume that (ii) holds. Let {a, b, c} be an arbitrary 3-element subset of E(H_{i}). Then, for each 2-element subset A of {a, b, c}, Lemma 3.3 implies that C ∪ A is a connected Tutte-line. Moreover, for the canonical partition {A, X_{A}, Y_{A}} of C ∪A, we must have that each of W_{1} and W_{2} is contained in X_{A} or Y_{A}. The fact that each of X_{A} and Y_{A} has two or three elements, but their union has at most five elements implies that A ∪ W_{1} or A ∪ W_{2} is a circuit of M. Hence there are distinct 2-element subsets A and A′ of {a, b, c} such that, for some j in {1, 2}, both A ∪ W_{j} and A′ ∪ W_{j} are circuits of M. Thus, if w ∈ W_{j}, then M has a circuit C_{1} contained in (A ∪ A′ ∪ W_{j}) − w. Since W_{j} is a 2-cocircuit of M|(C ∪ E(H_{i})), it follows that C_{1} is contained in and hence equals A ∪ A′. Therefore, as in case (i), we deduce that every 3-element subset of E(H_{i}) is a triangle, so r(E(H_{i})) = 2; a contradiction to (5).

3.8. Lemma. Suppose that i ∈ {1, 2, …, k} and that {a, b, c} is a 3-element subset of E(H_{i}). Then {a, b} is contained in a 4-circuit D of M where |D ∩ C| = 2. Moreover, either

(i) M has a triad that meets both {a, b} and D ∩ C; or (ii) E(H_{i}) is a triad of M and there is a triad of M that contains c and meets C. In both cases, M has a triad that meets both E(H_{i}) and C.

Proof. The fact that D exists follows immediately from Lemma 3.3(iii) since |C| ≤ 5. Let D ∩ C = {α, β}. Suppose that (i) does not occur. By Lemma 3.2, there are triads T and T′ of M that meet D. By Lemma 3.1(i), T ∩D ≠ T′∩D. The canonical partition of the connected Tutte-line {a, b}∪C must be {{a, b}, {α, β}, C −{α, β}}. Thus orthogonality and Lemma 3.1(ii) imply that each of |T ∩ (C ∪ {a, b})| and |T′ ∩ (C ∪ {a, b})| is 2. Hence we may assume, without loss of generality, that T ∩ (C ∪ {a, b}) = {a, b} and T′ ∩ (C ∪ {a, b}) = {α, β}. Therefore, by Lemma 3.6, E(H_{i}) = {a, b, c} and E(H_{i}) is a triad of M. We may suppose that the element of T′ − (C ∪ {a, b}) is not in C ∪ E(H_{i}) otherwise this element is c and (ii) follows.

Applying Lemma 3.2 again, this time to the circuit C, we deduce that M has a triad T′′ that meets C and is different from T′. By Lemma 3.5, |T′′ ∩ C| = 2. We show next that T′′ ∩ E(H_{i}) is empty. If not, then c ∈ T′′, or, by Lemma 3.1(ii), T′′ meets both {a, b} and D ∩ C. But, in both these cases, the lemma holds. Thus T′′ ∩ E(H_{i}) is indeed empty. Hence T′′ ∩ C is a 2-cocircuit of M|(C ∪ E(H_{i})). But T′ ∩ C is also a 2-cocircuit of M|(C ∪ E(H_{i})) and Lemma 3.1(i) implies that T′ ∩ C ≠ T′′ ∩ C. Hence M|(C ∪ E(H_{i})) has two 2-cocircuits contained in C. This contradiction to Lemma 3.7 completes the proof of Lemma 3.8.

3.9. Lemma. M has exactly two rank-one components, H_{i}. Moreover, |C| = 5 and r(M) = 6.

Proof. Suppose that the number n of rank-one components of M/C is at least three. Then, by Lemma 3.8, for each i in {1, 2, …, n}, there is a triad T_{i} such that both T_{i} ∩ C and T_{i} ∩ E(H_{i}) are non-empty. By Lemma 3.1(ii), if i and j are distinct members of {1, 2, …, n}, then T_{i} ∩ C ≠ T_{j} ∩ C. Thus M|(C ∪ E(H_{1})) has both T_{2} ∩ C and T_{3} ∩ C as 2-cocircuits contained in C, a contradiction to Lemma 3.7. We conclude that n ≤ 2. Thus

6 ≤ r(M) = |C| − 1 + n ≤ |C| + 1 ≤ 6,

so r(M) = 6. Moreover, n = 2 and |C| = 5.

We now work towards obtaining a final contradiction that will complete the proof of Theorem 1.5. By Lemma 3.8, for each i in {1, 2}, there is a triad T_{i} that meets both E(H_{i}) and C. If, for a fixed i, there are two such triads T_{i,1} and T_{i,2}, then, for j ≠ i, the sets T_{i,1} ∩ C and T_{i,2} ∩ C are 2-cocircuits of M|(C ∪ E(H_{j})). Thus, by Lemma 3.7, T_{i,1} ∩ C = T_{i,2} ∩ C, a contradiction to Lemma 3.1(ii). Hence T_{i} is unique.

Suppose that, for some i in {1, 2}, the set E(H_{i}) is not a triad of M. Then Lemma 3.8 implies that, for each 2-element subset A of E(H_{i}), there is a 4-element circuit, D_{A}, that contains A and meets C in exactly two elements. Thus, as (ii) of Lemma 3.8 does not hold, (i) of that lemma implies that there are at least two triads of M that meet C and E(H_{i}). This contradiction to the uniqueness of T_{i} implies that both E(H_{1}) and E(H_{2}) are triads of M.

Let E(H_{1}) = {a, b, c} and E(H_{2}) = {a′, b′, c′}. Without loss of generality, we may suppose that T_{1} ∩ E(H_{1}) = {c} and T_{2} ∩ E(H_{2}) = {c′}. Then, for some {α, β} ⊆ C, there is a circuit {α, β, a, b} of M. By orthogonality, either

(i) T_{1} = {α, β, c}; or (ii) T_{1} ∩ {α, β, a, b} = ∅. In both cases, we shall show that (iii) T_{1} ∩ T_{2} = ∅; and (iv) there are distinct elements μ and ν of T_{1} − c so that {a, c, ε, μ} and {b, c, ε, ν}

are circuits of M where ε is the element of C − (T_{1} ∪ T_{2}).

Suppose that (ii) occurs. Then, by Lemma 3.2, M has a triad T that meets {α, β, a, b} and is different from E(H_{1}). Since E(H_{1}) ∩ {α, β, a, b} = {a, b}, it follows, by Lemma 3.1(ii), that T ∩ {α, β, a, b} ≠ {a, b}. Thus either T meets both E(H_{1}) and C, or T ∩ {α, β, a, b} = {α, β}. Since T_{1} is the only triad meeting both E(H_{1}) and C, the first case implies that T_{1} = T; a contradiction since T_{1} avoids {α, β, a, b} by (ii). We conclude that T ∩ {α, β, a, b} = {α, β}. If T avoids E(H_{2}), then T_{1} ∩ C and T ∩ C are distinct 2-cocircuits of M|(C ∪ E(H_{2})) contained in C; a contradiction to Lemma 3.7. Thus T meets E(H_{2}). Since T also meets C, it follows that T = T_{2} and hence that T_{2} = {α, β, c′}. Hence T_{1} ∩ T_{2} = ∅, that is, (iii) holds. We may now assume that T_{1} = {γ, δ, c} where C = {α, β, γ, δ, ε}. By Lemma 3.3 and the fact that |C| = 5, the connected Tutte-line C ∪ {a, c} contains a 5-element circuit C_{1} of M that contains {a, c}. By applying Lemma 3.1(ii) to T_{1}, we deduce that |C_{1} ∩ {γ, δ}| = 1, say γ ∈ C_{1}. As T_{2} = {α, β, c′}, it follows that {α, β} is a series class of M|(C ∪ {a, c}) and hence that C_{1} = {α, β, γ, a, c}. Thus {a, c, δ, ε} is a circuit of M.

Now use the connected Tutte-line C ∪ {b, c} to give that M has a 5-element circuit C_{2} that contains {b, c}. Then, arguing as for C_{1}, we deduce that {b, c, δ, ε} or {b, c, γ, ε} is a circuit of M. The first possibility is excluded since it implies that {a, b, δ, ε} contains a circuit of M. This contradicts the fact that {{a, b}, {α, β}, {γ, δ, ε}} is the canonical partition of C ∪ {a, b}. We conclude that if (ii) occurs, then (iii) and (iv) hold.

Now suppose that (i) holds. Then, by Lemma 3.1(i) and (ii), T_{1} ∩ T_{2} = ∅, that is, (iii) holds. Thus we may assume that T_{2} = {γ, δ, c′}. Let C_{3} be a 5-element circuit of M|(C ∪ {a, c}) that contains {a, c}. Then, by applying Lemma 3.1(ii) to the triad {α, β, c}, we have that |C_{3} ∩ {α, β}| = 1, say α ∈ C_{3}. As T_{2} = {γ, δ, c′}, it follows that {γ, δ} is a cocircuit of M|(C ∪ {a, c}). Thus the canonical partition of C ∪ {a, c} is {{a, c}, {α, γ, δ}, {β, ε}}. Hence {a, c, β, ε} is a circuit of M. Arguing similarly using a 5-element circuit C_{4} of M|(C ∪ {b, c}) that contains {b, c}, we deduce that {b, c, β, ε} or {b, c, α, ε} is a circuit of M. The first possibility cannot occur because it implies that {a, b, β, ε} contains a circuit of M which contradicts the fact that {{a, b}, {α, β}, {γ, δ, ε}} is the canonical partition of C ∪ {a, b}. We conclude that {b, c, α, ε} is a circuit of M and hence that, when (i) occurs, both (iii) and (iv) hold.

Since {{a, b}, {α, β}, {γ, δ, ε}} is the canonical partition of C ∪ {a, b} and T_{1} ∩ T_{2} = ∅, Lemma 3.1(ii) implies that either T_{1} = {α, β, c} and T_{2} = {γ, δ, c′}, or T_{1} = {γ, δ, c} and T_{2} = {α, β, c′}. Using Lemma 3.1(ii) again, it follows that, in each case, either {{a′, b′}, {α, β, ε}, {γ, δ}} or {{a′, b′}, {α, β}, {γ, δ, ε}} is the canonical partition of C ∪ {a′, b′}. Thus {a′, b′, γ, δ} or {a′, b′, α, β} is a circuit of M. Using this circuit in place of {a, b, α, β}, and E(H_{2}) and T_{2} in place of E(H_{1}) and T_{1}, we may now argue as in (i) and (ii) above to deduce that there are distinct elements μ′ and ν′ of T_{2} − c′ such that {a′, c′, ε, μ′} and {b′, c′, ε, ν′} are circuits of M.

By elimination, ({a, c, ε, μ} ∪ {a′, c′, ε, μ′}) − ε contains a circuit C_{5} of M. The triads {a, b, c} and T_{1} and orthogonality imply that either C_{5} ∩ {a, c, μ} = ∅, or {a, c, μ} ⊆ C_{5}. Similarly, the triads {a′, b′, c′} and T_{2} imply that C_{5}∩{a′, c′, μ′} = ∅, or {a′, c′, μ′} ⊆ C_{5}. But |C_{5}| ≤ 5, so C_{5} is either {a, c, μ} or {a′, c′, μ′}. However, the connected Tutte-lines C ∪ {a, c} and C ∪ {a′, c′} imply that both {a, c, μ} and {a′, c′, μ′} are properly contained in circuits of M. This contradiction completes the proof of Theorem 1.5. □

To close this section, we shall present an example that shows that the lower bound on the rank in the hypothesis of Theorem 1.5 is best-possible. Let M be the tipless binary 5-spike, that is, M is the matroid that is represented over GF (2) by the matrix [I_{5}|J_{5} − I_{5}] where J_{5} is the 5 × 5 matrix of all ones. It is not difficult to show (see, for example, [11, p.321]) that M has circumference 5.

4. Removing circuits from matroids

In this section, we shall prove Theorems 1.6 and 1.7.

Proof of Theorem 1.6. By Lemma 2.1, there is a 3-connected matroid N having the same rank and the same circumference as M such that N = M|E(N) and

|E(N)| ≤ 2r(M) + max{0, r(M) − c(M)}.

Now

|E(M)| − |E(N)| ≥ [3r(M) + 1 + max{0, r(M) − c(M)}]
−[2r(M) + max{0, r(M) − c(M)}]
= r(M) + 1.

Thus E(M) − E(N) must be a dependent set of M and so contains a circuit C of M avoiding E(N). Observe that M\C is a 3-connected matroid, since it has N as a minor and E(N) spans M. □

On combining the last theorem with Theorem 1.5, we immediately obtain the following result.

4.1. Corollary. If M is a 3-connected matroid such that r(M) ≥ 6 and

|E(M)| ≥ 4r(M) − 5,

then M has a circuit C such that M\C is 3-connected.

The last corollary is best-possible as the next example shows. Let M be the matroid that is obtained as follows. Begin with a 3-point line {a, b, c} and take the generalized parallel connection of n copies, N_{1}, N_{2}, …, N_{n}, of M(K_{4}) across {a, b, c}. Each N_{i} has a unique 3-point line that meets {a, b, c} at a. Freely add a point p_{i} on each such line. Then M is obtained by deleting a from the resulting matroid. Certainly M is 3-connected and has rank 2 + n. Moreover, for each i, the 4-element set (E(N_{i}) ∪ p_{i}) − {a, b, c} is a cocircuit of M containing a triangle. Using this fact and orthogonality, it is not difficult to see that M has no circuit whose deletion leaves a 3-connected matroid. But

|E(M)| = 4n + 2 = 4(n + 2) − 6 = 4r(M) − 6,

so the bound in the last corollary cannot be improved.

The proof of Theorem 1.7 is obtained by making slight modifications to the proof of Theorem 1.6 so that Theorem 1.2 rather than Lemma 2.1 can be used. We omit the straightforward details.

To obtain an example showing that Theorem 1.7 is best-possible, we modify the previous example by freely adding two new points q_{1} and q_{2} on the line {b, c}. Let the resulting matroid be M′. Then |E(M′)| = 4n + 4 and r(M′) = n + 2, so |E(M′)| = 4r(M′)−4. For each i, let b_{i} be the coloop of M′|[(E(N_{i})∪p_{i})−{a, b, c}] and let B = {b, c, b_{1}, b_{2}, …, b_{n}}. Then B is a basis for M′ and, arguing as for M, it is not difficult to see that M′ has no circuit C that avoids B such that M′\C is 3-connected.

SIZE, CIRCUMFERENCE AND CIRCUIT REMOVAL IN 3–CONNECTED MATROIDS 11

Acknowledgements The first author was partially supported by CNPq, CAPES, FINEP and PRONEX 107/97. The second author was partially supported by the National Security Agency.

References

[1] Cunningham, W.H., A combinatorial decomposition theory, Ph. D. thesis, University of Waterloo, 1973.

[2] Dirac, G.A., Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952), 69–81.

[3] Halin, R., Zur Theorie der n-fach zusammenhängenden Graphen, Abh. Math. Sem. Univ. Hamburg 33 (1969), 133–164.

[4] Jackson, B., Removable cycles in 2-connected graphs of minimum degree at least four, J. London Math. Soc. (2) 21 (1980), 385–392.

[5] Lemos, M. and Oxley, J., On removable circuits in graphs and matroids, J. Graph Theory, to appear.

[6] Lemos, M. and Oxley, J., On packing minors into connected matroids, Discrete Math., to appear.

[7] Lemos, M. and Oxley, J., On the 3-connected matroids that are minimal having a fixed spanning restriction, submitted.

[8] Lemos, M., Oxley, J., and Reid, T.J., On the 3-connected matroids that are minimal having a fixed restriction, submitted.

[9] Mader, W., Kreuzungfreie a, b-Wege in endlichen Graphen, Abh. Math. Sem. Univ. Hamburg 42 (1974), 187–204.

[10] Oxley, J.G., On matroid connectivity, Quart. J. Math. Oxford Ser. (2) 32 (1981), 193–208.

[11] Oxley, J.G., Matroid theory, Oxford University Press, New York, 1992.

[12] Tutte, W.T., Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1–47.

Departamento de Matemática, Universidade Federal de Pernambuco, Recife, Pernambuco 50740-540, Brazil

  E-mail address: manoel@dmat.ufpe.br

Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803–4918, USA

  E-mail address: oxley@math.lsu.edu