For which graphs does every edge belong to exactly two chordless

cycles?

Uri N. Peled^{1} and Julin Wu^{2}

Dept. of Mathematics, Statistics, and Computer Science

(M/C 249)

The University of Illinois at Chicago 851 S. Morgan Street Chicago, IL 60607-7045

Submitted: December 2, 1995; Accepted: April 15, 1996.

Key Words: Chordless cycles, balanced graphs, balanced matrices

Mathematical Reviews Subject Numbers: Primary 05C75; Secondary 05C3B, 05C50, 90C35

1uripeled@uic.edu 2jwu2@uic.edu

Abstract

A graph is 2-cycled if each edge is contained in exactly two of its chordless cycles. The 2-cycled graphs arise in connection with the study of balanced signing of graphs and matrices. The concept of balance of a {0, +1, −1}- matrix or a signed bipartite graph has been studied by Truemper and by Conforti et al. The concept of α-balance is a generalization introduced by Truemper. Truemper exhibits a family F of planar graphs such that a graph G can be signed to be α-balanced if and only if each induced subgraph of G in F can. We show here that the graphs in F are exactly the 2-connected 2-cycled graphs.

1 Introduction

A graph is said to be 2-cycled if each of its edges is contained in exactly two chordless cycles. The 2-cycled graphs arise in connection with the study of balanced signing of graphs and matrices by Truemper [3] and by Conforti et al. [2], as indicated in the next three paragraphs.

A signed graph is a graph G = (V, E) together with a mapping f : E ⟶ {+1, −1}. Consider a mapping α : C ⟶ {0, 1, 2, 3}, where C is the set of chordless cycles of G. If Σ_{e∈C}f(e) ≡ α(C) (mod 4) for all C ∈ C, we say that the signed graph is α-balanced. A trivial necessary condition, which we assume throughout, is that |C| ≡ α(C) (mod 2) for all C ∈ C. When α = 0, this condition means that G is bipartite, in which case it can be specified by its adjacency matrix A, and A is balanced in the usual sense if and only if the signed graph consisting of G and the constant mapping f = 1 is 0-balanced. Similarly, a {0, +1, −1}-matrix A specifies a signed bipartite graph, and A is said to be balanced when the signed bipartite graph is 0-balanced.

It is easy to check that each graph of the following types is 2-cycled (See Figure 1):

Star-subdivision of K_{4}: The result of subdividing zero or more of the three edges incident to a single vertex of K_{4};

Rim-subdivision of a wheel: The result of subdividing zero or more rim edges of the wheel W_{k}, k ≥ 3;

Subdivision of K_{2,3}: The result of subdividing zero or more edges of K_{2,3}.;

Triangles-joining: Two vertex-disjoint triangles with three vertex-disjoint paths joining them.

Note that if two nonadjacent edges of K_{4} and possibly other edges are subdivided, the resulting graph is not 2-cycled. It is called a bad subdivision of K_{4}. Truemper [3] showed that a graph G possesses a mapping f that makes it α-balanced if and only if each induced subgraph of G that is a starsubdivision of K_{4}, a rim-subdivision of a wheel, a subdivision of K_{2,3} or a triangles-joining enjoys the same property. Our main result is that these are all the 2-connected 2-cycled graphs (Clearly, a graph s 2-cycled if and only if all its 2-connected components are, so without loss of generality we may consider only 2-connected graphs):

Figure 1: 2-cycled graphs. (a): Star-subdivision of K_{4}; (b): Rim-subdivision of a wheel; (c): Subdivision of K_{2,3}; (d): Triangles-joining.

Theorem 1 (Main Theorem) A 2-connected graph is 2-cycled if and only if it is a star-subdivision of K_{4}, a rim-subdivision of a wheel, a subdivision of K_{2,3} or a triangles-joining.

This paper is organized as follows. In Section 2 we give definitions of some new concepts. In Section 3 we define and characterize the upper and lower 2-cycled graphs; these graphs are defined so that a graph is 2-cycled if and only if it is both upper 2-cycled and lower 2-cycled. In Section 4 we study the structure of 2-cycled graphs and prove the Main Theorem. Early on (in Corollary 2) we show that the upper 2-cycled graphs are planar, and this planarity plays an important part in the proofs.

2 Preliminaries

We discuss only finite simple graphs and use standard terminology and notation from [1], except as indicated. We denote by N_{G}(u) or simply N(u) the set of vertices adjacent to a vertex u in a graph G, and by N_{G}(S) or N(S) the set ⋃_{u∈S} N_{G}(u) for a vertex subset S. A chord of a path or a cycle is an edge joining two non-consecutive vertices of the path or cycle. A chordless path or cycle is one having no chord. For a path P = (x_{1}, x_{2}, …, x_{k}), we use the notation P [x_{i}, x_{j}] for the subpath (x_{i}, …, x_{j}), where 1 ≤ i < j ≤ n. If e = ab is an edge of G, the contraction G/e of G with respect to e is the graph obtained from G by replacing a and b with a new vertex c and joining c to those vertices that are adjacent to a or b. The edge set of G/e may be regarded as a subset of the edge set of G. A minor of G is a graph that can be obtained from G by a sequence of vertex-deletions, edge-deletions and contractions. By subdividing an edge e we mean replacing e by a path P joining the ends of e, where P has length at least 2 and all of its internal vertices have degree 2. A subdivision of G is a graph obtained by subdividing zero or more of the edges of G. The intersection (union) G_{1} ∩G_{2} (G_{1} ∪G_{2}) of graphs G_{1} = (V_{1}, E_{1}) and G_{2} = (V_{2}, E_{2}) is the graph with vertex set V_{1} ∩ V_{2} (V_{1} ∪ V_{2}) and edge set E_{1} ∩ E_{2} (E_{1} ∪ E_{2}). If C_{1} and C_{2} are cycles of a plane graph G, we say that C_{1} is within (surrounds) C_{2} if the area enclosed by C_{1} is contained in (contains) that enclosed by C_{2}.

Two cycles C and C′ are said to be harmonic if C ∩ C′ is a path, as illustrated in Figure 2. If C and C′ are harmonic cycles of a plane graph, we can find an appropriate plane drawing of the graph such that C′ is within C, if it is not already the case, by selecting a face within C and making it the outer face.

Figure 2: Harmonic cycles.

Let C and C′ be two cycles with a common edge e, and u a vertex of C′ − C. Let P′ be the maximal subpath of C′ that contains u and does not have internal vertices on C, and let P be the subpath of C joining the two ends of P′ and containing e. Then P′ ∪ P is a cycle C′′, as illustrated in Figure 3. The operation transforming C′ into C′′ is called grafting C′ with respect to C, e and u. An important property of this operation is that the new cycle C′′ is harmonic with C. Furthermore, if the graph is a plane graph and u is within C (or C′ surrounds C), then C′′ is within (surrounds) C.

Figure 3: Grafting.

Let P = (x_{1}, x_{2}, …, x_{k}) be a path in G. If P has a chord x_{i}x_{j} for some i < j −1, we can obtain another path P′ = (x_{1}, …, x_{i}, x_{j}, …, x_{k}) by deleting the vertices between x_{i} and x_{j} and adding the edge x_{i}x_{j} to P. If P′ still has chords, we can apply the same operation to P′, and so on until we obtain a chordless path P^{∗} connecting x_{1} to x_{k}. For a cycle C of G and an edge e of C, we can apply the above operation to C − e to obtain a chordless cycle C^{∗} containing e. We call the operation transforming C into C^{∗} chord-cutting C with respect to e. We note that if the graph is a plane graph and C surrounds (is within, is harmonic with) a chordless cycle Ĉ and e is a common edge of C and Ĉ, then the cycle obtained by chord-cutting C with respect to e again surrounds (is within, is harmonic with) Ĉ.

Let C and C′ be cycles of G, where C is chordless, e a common edge of C and C′, and u a vertex of C′ − C. By grafting C′ with respect to C, e and u, and then chord-cutting the resulting cycle with respect to C and e, we obtain a chordless cycle C^{∗}. We call the operation transforming C′ into C^{∗} harmonizing C′ to C with respect to e and u. Note that the new cycle C^{∗} still contains e and is harmonic with C and chordless. Furthermore, if G is a plane graph and u is within C (C′ surrounds C), then C^{∗} is within (surrounds) C. After the harmonization operation we forget C′ and rename C^{∗} as C′.

3 Upper and lower 2-cycled graphs

We say that a graph is upper (lower) 2-cycled if each of its edges is contained in at most (at least) two of its chordless cycles. Clearly, a graph possesses this property if and only if each 2-connected component does, but in the rest of this section we do not assume 2-connectivity. The following lemma is crucial in characterizing upper 2-cycled graphs.

Lemma 1 If G = (V, E) is upper 2-cycled, so are its minors.

Proof. It suffices to show that if G′ results from G by deleting or contracting an edge uv and G′ is not upper 2-cycled, neither is G. Let e = ab be an edge of G′ that is contained in distinct chordless cycles C′_{1}, C′_{2} and C′_{3} of G′. Case 1: G′ = G − uv. Note that if uv is not a chord of C′_{i}, then C′_{i} is also a chordless cycle of G; in this case, we put C_{i} = C′_{i}. If uv is a chord of C′_{i}, then C′_{i} ∪ uv is split into two chordless cycles of G, each consisting of uv and a subpath of C′ connecting u to v; we call the one containing e C_{i} and the other one C̃_{i}. If C_{1}, C_{2} and C_{3} are distinct, then they are distinct chordless cycles of G containing e. If they are not, we may assume C_{1} = C_{2}. Then C′_{1} and C′_{2} must have uv as a chord, and C_{1}, C̃_{1} and C̃_{2} are distinct chordless cycles of G containing uv. Case 2: G′ = G/uv. The edge uv of G is contracted to a vertex w of G′. Because uv ≠ ab, {a, b}∩{u, v} is empty or has one vertex. If it is nonempty, we assume u = a without loss of generality.

If E(C′_{i}) forms a cycle of G, it must be a chordless cycle, and we let C_{i} be that cycle. If not, w must be a vertex of C′_{i}, and E(C′_{i}) forms a path P_{i} in G connecting u to v. Let u′_{i}, v′_{i} be the neighbors of u, v on P_{i}, respectively. Then P_{i} ∪ uv forms a cycle C_{i}^{∗} of G, and its only possible chords are uv′_{i} and u′_{i}v. By chord-cutting C_{i}^{∗} with respect to e, we find a chordless cycle C_{i} containing e.

Note that if e and uv are not adjacent, or if the chord u′_{i}v does not exist, then E(C_{i}) is contracted to E(C′_{i}) when we contract the edge uv.

Now we have three chordless cycles C_{1}, C_{2} and C_{3} containing e. If they are not all distinct, say C_{1} = C_{2}, then C_{1} is the triangle {u = a, v, b = u′_{1} = u′_{2}}, C_{1}^{∗} and C_{2}^{∗} both have bv as a chord, and bv is contained in three distinct chordless cycles of G, namely {a, v, b}, bv ∪ P′_{1} − e, bv ∪ P′_{2} − e. ■

We note that K_{3,3} − e and K_{2} ⊕ 3K_{1} (the graph obtained by joining every vertex of K_{2} to every vertex of 3K_{1}) are not upper 2-cycled. These graphs are illustrated in Figure 4. Therefore we have the following corollary of Lemma 1.

Figure 4: Forbidden minors of upper 2-cycled graphs.

Corollary 1 An upper 2-cycled graph contains no K_{2} ⊕ 3K_{1} or K_{3,3} − e as a minor.

Note that K_{2} ⊕ 3K_{1} is a minor of K_{5} and K_{3,3} − e is a minor of K_{3,3}. By Kuratowski’s Theorem, we have the following consequence of Corollary 1.

Corollary 2 An upper 2-cycled graph must be planar.

The next theorem characterizes the upper 2-cycled graphs. Although we only use its necessity part to prove the Main Theorem, it has an independent interest.

Theorem 2 A graph is upper 2-cycled if and only if it contains no K_{2} ⊕3K_{1} or K_{3,3} − e as a minor.

Proof. The necessity is Corollary 1 above. Now we prove the sufficiency. By the argument leading to Corollary 2, G must be planar. Assume that, if possible, G is not upper 2-cycled. We assert that G has three cycles C_{1}, C_{2} and C_{3} and an edge e such that the following properties hold for an appropriate plane drawing of G:

1. C_{1}, C_{2} and C_{3} are distinct chordless cycles containing e;

2. C_{2} is within C_{1} and C_{3} is within C_{2};

3. C_{1}, C_{2} and C_{3} are harmonic with each other.

In proving the assertion, we make use of a weaker version of Property 3, namely,

4. C_{2} is harmonic with C_{1} and C_{3}.

By the assumption that G is not upper 2-cycled, it has three cycles C_{1}, C_{2} and C_{3} and an edge e satisfying Property 1. If two of the cycles are harmonic, we rename them as C_{1} and C_{3}. If not, we harmonize C_{3} to C_{1} with respect to e, and the new C_{3} is still different from C_{1} and C_{2}. In any case, we may assume C_{3} is within C_{1}. For the new C_{1}, C_{2} and C_{3}, Property 1 still holds, but now C_{3} is within and harmonic with C_{1}.

Next, let us consider three cases about C_{2}. Case 1: C_{2} has a vertex u inside C_{3}. We harmonize C_{2} to C_{3} with respect to u and e, and switch the names of C_{3} and C_{2}. The cycles C_{1}, C_{2} and C_{3} now satisfy Properties 1, 2 and 4. Case 2: C_{2} has a vertex u outside C_{1}. We select a face within C_{3}, make it the outer face, and switch the names of C_{1} and C_{3}, and we are back to Case 1. Case 3: C_{2} is between C_{1} and C_{3}. We harmonize C_{1} to C_{2} and C_{3} to C_{2} with respect to e. The cycles C_{1}, C_{2} and C_{3} now satisfy Properties 1, 2 and 4.

Thus in all cases, Properties 1, 2 and 4 hold for C_{1}, C_{2}, C_{3} and e. By planarity and Property 2 we have C_{1} ∩ C_{3} ⊂ C_{2}, hence C_{1} ∩ C_{3} = (C_{1} ∩ C_{2}) ∩ (C_{2} ∩ C_{3}). Since each of C_{1} ∩ C_{2} and C_{2} ∩ C_{3} is a subpath of C_{2}, C_{1} ∩ C_{3} must be a path or the union of two disjoint paths. In the former case, C_{1} is harmonic with C_{3}, as required. In the latter case, illustrated in Figure 5, the symmetric difference of E(C_{2}) and E(C_{3}) forms a cycle C′, and we can find an edge e′ in C_{1} ∩ C_{2} such that e′ is also on C′. Renaming C′ as C_{3} and e′ as e and chord-cutting C_{3} with respect to the new edge e, we achieve Property 3 for the new C_{1}, C_{2}, C_{3} and e while Properties 1 and 2 remain valid. This completes the proof of the assertion.

It follows from the assertion that P_{13} = C_{1} ∩ C_{3} is a path contained in C_{2} and containing e. Let P′_{13} (P′_{31}) be the subpath of C_{1} − e (C_{3} − e) between the ends a and b of P_{13}.

Suppose no internal vertex of P′_{31} is on C_{2}. Let P′_{13} = (a = x_{0}, x_{1}, …, x_{k} = b), and let i (j) be the largest (smallest) index such that x_{0}, …, x_{i} (x_{j}, …, x_{k}) are on C_{2}, as illustrated in Figure 6. Since C_{1} and C_{2} are chordless, P′_{31} and P′_{13}[x_{i}, x_{j}] are not single edges, i.e., each has an internal vertex. For the same reason, the subpath of C_{2} from x_{i} to x_{j} that does not contain e has

Figure 5: An illustration for the proof of the assertion.

an internal vertex. We contract x_{0}, …, x_{i} into one vertex and x_{j}, …, x_{k} into another vertex, and now C_{1} ∪ C_{2} ∪ C_{3} is a subdivision of K_{2} ⊕ 3K_{1}, which has K_{2} ⊕ 3K_{1} as a minor, contrary to the hypothesis. A similar argument holds if no internal vertex of P′_{13} is on C_{2}.

Figure 6: An illustration for the proof of Theorem 2.

If both P′_{13} and P′_{31} have an internal vertex on C_{2}, there is a subpath P of C_{2} connecting an internal vertex d of P′_{13} to an internal vertex c of P′_{31} such that P has no internal vertex on C_{1} or C_{3}. Without loss of generality, we assume that the cycle C_{2} passes through the vertices a, b, c, d in this order. Then, since C_{2} is harmonic with both C_{1} and C_{3}, C_{2} must be P_{13}[a, b] ∪ P′_{31}[b, c]∪P [c, d]∪P′_{13}[d, a], as illustrated in Figure 7. Because C_{2} is a chordless cycle, each of P′_{13}[b, d] and P′_{31}[a, c] has an internal vertex. Hence C_{1} ∪C_{2} ∪C_{3} is a bad subdivision of K_{4}, which can always be contracted to K_{3,3} − e, contrary to the hypothesis. ■

Figure 7: An illustration for the proof of Theorem 2.

The next theorem characterizes the lower 2-cycled graphs. The proof is simple and is omitted.

Theorem 3 A graph G is lower 2-cycled if and only if G has no bridges and every chordless cycle C of G satisfies at least one of the following conditions:

1. For each edge e = uv of C, G − V (C) has a connected component H such that N(H) ∩ V (C) = {u, v};

2. G − V (C) has a connected component H such that N(H) contains a pair of non-consecutive vertices of C;

3. C is a triangle, and G − V (C) has a connected component H such that V (C) ⊆ N(H).

4 Proof of the Main Theorem

We only need to prove the “only if” part of the Main Theorem. We do so by establishing a series of properties that a 2-connected 2-cycled graph G must possess.

By Corollary 2, we have the following:

Property 1 G is planar.

Property 2 For each edge ab of G, G − {a, b} has at most two connected components.

Indeed, otherwise there would be three chordless cycles containing ab.

We call an edge ab critical if G − {a, b} has exactly two connected components.

Let F be any face of a plane drawing of G. The boundary of F is a cycle C by 2-connectivity, and we call it a face-cycle. If F is the outer face of a plane drawing D of G, we call C the outer cycle of D. Suppose the outer cycle C has a critical edge ab. We denote by H the connected component of G − {a, b} not containing the other vertices of C. By 2-connectivity we have N(H)∩V (C) = {a, b}. We can find another plane drawing D′ of G by moving H outside of C. If C′ denotes the new outer cycle, then V (C′) ⊃ V (C), and ab is a chord of C′, rather than an edge of it. We call the operation transforming D into D′ flipping. If C′ still has critical edges, we repeat this operation. In a finite number of steps, we obtain a plane drawing of G whose outer cycle C^{∗} has no critical edges. We now assert that C^{∗} is chordless. If not, a chord ab would spilt the cycle C^{∗} into two cycles C′ and C′′, and we may assume that C′ is chordless. There must be a vertex u within C′, for otherwise there would be no other chordless cycles containing an edge from C′−ab. Let H be the connected component of G − V (C′) containing u. The set N(H) ∩ V (C′) cannot be the two ends of an edge from C′ − ab, because by Property 2 such an edge would be a critical edge on the outer cycle C^{∗}. Thus C′ does not satisfy Condition 1 of Theorem 3, and it must satisfy Condition 2 or 3. We can therefore find a chordless path P connecting two non-consecutive vertices of the path C′ − ab such that all the internal vertices of P are from H, as illustrated in Figure 8. It is easy to see that C^{∗} ∪ {ab} ∪ P can be contracted to K_{2} ⊕ 3K_{1}, contradicting Corollary 1. This proves the assertion.

Recall that the flipping operation adds a new chord of the new outer cycle. Hence by the assertion, no flipping ever takes place, and the outer cycle C of the arbitrary drawing D is chordless. Since each face of a plane drawing can be drawn as the outer face, we have established the following two properties:

Property 3 G has no critical edge.

Figure 8: An illustration for the proof of the assertion.

Property 4 In each plane drawing of G, each face-cycle is chordless.

In each plane drawing, each edge e belongs to two face-cycles by 2connectivity. The latter are chordless by Property 4, and must be the only chordless cycles containing e since G is 2-cycled. We therefore conclude the following:

Property 5 In each plane drawing of G, each chordless cycle is a face-cycle.

Another property of G is given below.

Property 6 At least one of the face-cycles is not a triangle if G ≠ K_{4}.

Suppose to the contrary that every face-cycle of G is a triangle. Let C be the outer cycle with vertices a, b and c. Without loss of generality, let k ≥ 3 be the degree of a, and let ax_{1}, ax_{2}, …, ax_{k} be the edges incident with a in counterclockwise order, where b = x_{1} and c = x_{k}. Then by our assumption, x_{1}x_{2}, x_{2}x_{3}, …, x_{k−1}x_{k} must be edges of G, as illustrated in Figure 9.

If k ≥ 4, there is an edge e = x_{i}x_{j}, j − i > 1, e ≠ x_{1}x_{k}, for otherwise {x_{1}, …, x_{k}} is a chordless cycle, hence a face-cycle by Property 5, but it is not a triangle. But then the triangle {a, x_{i}, x_{j}} is not a face-cycle, contradicting Property 5. Therefore k must be 3, and for each {p, q, r} ⊆ {a, x_{1}, x_{2}, x_{3}}, the triangle {p, q, r} is a face-cycle by Property 5. Therefore G has no other vertices, and so G = K_{4}.

By Property 6, we may assume that we have chosen a plane drawing of G whose outer cycle C has length at least 4. We make this assumption

Figure 9: An illustration for the proof of Property 6.

for the rest of the proof, and use the notations N_{C}(u) = N(u) ∩ V (C) and N_{C}(S) = N(S) ∩ V (C) for a vertex u and a vertex-subset S.

Property 7 For each connected component H of G−V (C), N_{C}(H) contains a pair of non-consecutive vertices along C.

In fact, N_{C}(H) cannot be empty or a single vertex by 2-connectivity. Neither can it be the two ends of an edge e of C, since otherwise e would be a critical edge by Property 2, contrary to Property 3. Therefore N_{C}(H) contains a pair of non-consecutive vertices along C.

Property 8 G − V (C) is connected.

If not, G − V (C) would have at least two connected components H_{1} and H_{2}. For i = 1, 2, N_{C}(H_{i}) contains a pair of non-consecutive vertices a_{i}, b_{i} on C by Property 7. we can find a path P_{i} connecting a_{i} to b_{i} all of whose internal vertices are from H_{i}. By planarity, P_{1} and P_{2} do not intersect except possibly at the ends. Therefore the minor C ∪ P_{1} ∪ P_{2} can be contracted to K_{2} ⊕ 3K_{1}, contrary to Corollary 1.

Property 9 G − V (C) contains no cycle.

If G − V (C) contains a cycle, it must contain a chordless cycle C′. There exists vertex-disjoint paths P_{1} and P_{2} between C and C′ (this can be seen by adding a new vertex s adjacent to every vertex of C and another new vertex t adjacent to every vertex of C′ without destroying 2-connectivity, and then applying Menger’s Theorem to s and t). Let x_{i} and y_{i} be the ends of P_{i} on C and C′, respectively.

If x_{1} and x_{2} are not consecutive along C, let y′ be a third vertex on C′, and let e be any edge of the subpath of C′ from y_{1} to y_{2} that avoids y′, as illustrated in Figure 10. Then e belongs to three chordless cycles of the minor C ∪ C′ ∪ P_{1} ∪ P_{2}, contrary to Lemma 1.

Figure 10: An illustration for the proof of Property 9.

Therefore we may assume that x_{1} and x_{2} are consecutive along C, and similarly y_{1} and y_{2} are consecutive along C′. Then since the edge x_{1}x_{2} of C is not critical by Property 3, G − {x_{1}, x_{2}} has a shortest path P_{3} from C to C′. Let x_{3} and y_{3} be the ends of P_{3} on C and C′, respectively. If P_{3} and P_{1} ∪ P_{2} are disjoint, then since C has at least four vertices, we can forget P_{1} or P_{2} and then we are back to the previous case. Otherwise, let z be the first vertex of P_{3} that belongs to P_{1} ∪ P_{2}. We may assume without loss of generality that z is on P_{1}, as illustrated in Figure 11. Consider the minor M = C ∪ C′ ∪ P_{1} ∪ P_{2} ∪ P_{3}[x_{3}, z] of G. The edge y_{1}y_{2} is on three chordless cycles of M, namely C′, P_{1} ∪ P_{2} ∪ {x_{1}x_{2}, y_{1}y_{2}}, and P_{3}[x_{3}, z] ∪ P_{1}[z, y_{1}] ∪ {y_{1}y_{2}} ∪ P_{2} ∪ P′, where P′ is the subpath of C from x_{2} to x_{3} that avoids x_{1}. This contradicts Lemma 1, thereby proving Property 9.

By Property 8 and Property 9, G − V (C) is a tree T.

Property 10 T must be a path.

If T is not a path, it has a vertex v such that deg_{T} (v) ≥ 3. By Property 7, N_{C}(T) has two non-consecutive vertices a and b along C. The forest T − v

Figure 11: An illustration for the proof of Property 9.

has connected components T_{1} and T_{2} (possibly identical) such that {a} ⊆ N_{C}(T_{1})∪N_{C}(v) and {b} ⊆ N_{C}(T_{2})∪N_{C}(v). Let T_{3} be a connected component of T − v distinct from T_{1} and T_{2}. Since v is not a cut vertex of G by 2connectivity, there exists a vertex c ∈ N_{C}(T_{3}). Let P be a path from v to c via T_{3}, as illustrated in Figure 12.

Figure 12: An illustration for the proof of Property 10.

We contract T − T_{3} to a single vertex w, which becomes an end of P. Consider the minor M = C∪P ∪{wa, wb} of G. If c ≠ a, b, then, as illustrated in Figure 13 (a), M is a bad subdivision of K_{4}, which is not upper 2-cycled. Otherwise we may assume that c = a, as illustrated in Figure 13 (b), and we contract the edge wb of M to obtain a subdivision of K_{2} ⊕ 3K_{1}, which is not upper 2-cycled. In both cases, Lemma 1 is contradicted.

Figure 13: Illustrations for the proof of Property 10. (a): c ≠ a, b; (b): c = a.

Property 11 If u and v are the two ends of the path T and u ≠ v, then N_{C}(u) and N_{C}(v) are nonempty, and each of N_{C}(T − u) and N_{C}(T − v) consists of either a single vertex or a pair of consecutive vertices along C.

The sets N_{C}(u) and N_{C}(v) (and hence also N_{C}(T − u) and N_{C}(T − v)) are nonempty by 2-connectivity. Assume that N_{C}(T − v) contains nonconsecutive vertices a and b along C. We contract T − v to a vertex w, and let P be a path from w to C via v. Then we argue about the minor M = C ∪ P ∪ {wa, wb} as in Property 10. Similarly, N_{C}(T − u) has no non-consecutive vertices along C.

Now we are ready to list all the possible 2-connected 2-cycled graphs, and thereby prove Theorem 1, by considering all possibilities for T. Case 1: T is a single vertex v. Then G is a rim-subdivision of a wheel W_{k} with k ≥ 3 if deg_{G}(v) ≥ 3, and by Property 7 G is a subdivision of K_{2,3} if deg_{G}(v) = 2. Case 2: V (T) = {u, v}. If each of N_{C}(u) and N_{C}(v) has only one vertex, then the two vertices are distinct and non-consecutive by Property 7, so G is a subdivision of K_{2,3}. If one of N_{C}(u) and N_{C}(v) has one vertex and the other has two (necessarily consecutive by Property 11), then N_{C}(u) ∩ N_{C}(v) = ∅ by Property 7 and so G is a star-subdivision of K_{4}. If both N_{C}(u) and N_{C}(v) (distinct by Property 7) have two vertices (necessarily consecutive by Property 11), then G is a triangles-joining or a rim-subdivision of the wheel W_{4} depending on whether N_{C}(u) ∩ N_{C}(v) is empty or not. Case 3: T is a path of length at least 2, with ends u, v. Neither N_{C}(T −u) nor N_{C}(T − v) contains a pair of non-consecutive vertices of C by Property 11, whereas N_{C}(T) does by Property 7. So N_{C}(u)∪N_{C}(v) must contain a pair a, b of non-consecutive vertices, with a ∈ N_{C}(u) and b ∈ N_{C}(v). Moreover, N_{C}(x) does not meet {a, b} for any internal vertex x of T. If y ∈ N_{C}(x) for some internal vertex x of T, then by the above and Property 11, y must be different from and adjacent to both a and b. For the same reason, N_{C}(u) ⊆ {y, a} and N_{C}(v) ⊆ {y, b}, and N_{C}(z) ⊆ {b, y} ∩ {a, y} = {y} for all internal vertices z of T. Therefore G must be a rim-subdivision of a wheel with center y. If N_{C}(x) is empty for every internal vertex x of T, then the argument is similar to the one of Case 2. ■

References

[1] J.A. Bondy and U.S.R. Murty. Graph Theory with Applications. 1976. Macmillan, London, 1976.

[2] M. Conforti, G. Cornuéjols, A. Kapoor, K. Vušković, and M.R. Rao. Balanced matrices. In J.R. Birge and K.G. Murty, editors, Mathematical Programming State of the Art 1994, pages 1–33. The University of Michigan, 1994.

[3] K. Truemper. Alpha-balanced graphs and matrices and GF (3)-repre-sentability of matroids. Journal of Combinatorial Theory B, 32:112–139,