Proving the Existence of Even Cycles in Graphs with Nodes of Minimum Degree 3

In graph theory, a fundamental question arises when considering graphs where each node has a minimum degree of 3. Specifically, the question of whether such a graph must contain at least one cycle with an even number of nodes is a classic problem that has both theoretical and practical implications. In this article, we will explore and prove this statement.

Introduction

Given a graph G with at least two vertices, where all but at most one vertex satisfies a minimum degree requirement of at least 3, we will prove that G must contain at least one cycle of even length. This proof relies on graph traversal, bipartite graph properties, and the concept of minimal counterexamples.

The Bipartite Tree Argument

To begin the proof, we start with a spanning tree T of the graph G. Since T is a tree and therefore bipartite, we can label the vertices alternately as A and B. Suppose there are no even cycles in G. In this case, every edge in the original graph G that is not in T must connect vertices of the same label, i.e., A vertices to A vertices or B vertices to B vertices. If we take a terminal vertex u of T and suppose it is an A vertex, then since the degree of u is at least 3, it is adjacent to at least two other A vertices v and w. On the tree, there is a shortest path from v to w that cannot go through u. This shortest path has an even number of edges, as a shortest path in a bipartite graph with alternating labels will always have an even number of edges. When we add the edges uv and uw to this path, we form an even cycle.

General Proof

We will now prove the statement for finite simple graphs, defined as graphs with no loops.

Claim 1: Even Cycle Existence

Suppose a graph G contains a cycle C such that two of its vertices, x and y, are joined by a path P with no common edges between P and C. We will prove that G contains a cycle of even length.

Assume, without loss of generality, that P has the smallest length among all paths with edges in (E(G) - E(C)) joining two points on V(C).

Then P must go through precisely two of C's vertices otherwise P could be cut into two smaller paths leading to a contradiction. Cutting C into two paths, say (C_1) and (C_2), we see that the following are cycles: (C_1 cup P), (C_2 cup P), and (C_1 cup C_2 cup P P). The sum of the edge lengths of these cycles is even, so one of the three must be even, as the sum of three odd numbers would be odd.

Claim 2: Cycle Existence

Suppose a graph G with at least two vertices satisfies (N(x) geq 3) for all but at most one vertex x, where (N(x)) is the set of neighbors of x. We will prove that G contains a cycle.

By the handshaking lemma, G contains at least (frac{3}{2}n - 1) edges, where n is the number of vertices in G. Since (n geq 2), G contains a vertex x with (N(x) geq 3) implying that (n geq 4). Therefore, (frac{3}{2}n - 1 geq n), so G has at least (n) edges and the claim follows.

Even Cycle Existence Proof

Assume that G was a counterexample with n minimal. Let y (in) V(G) such that for all vertices x ( eq) y, one has (N(x) geq 3).

By Claim 2, G contains a cycle C. Let (V(C) {x_1, ldots, x_k}) where (k geq 3).

Let G' be the graph obtained from G by deleting all edges in E(C). We claim that any two of the (x_i) must lie in distinct connected components of G'. Else we would be done by Claim 1 already.

So we can split G' into k disjoint subgraphs (G'_1, ldots, G'_k) so that (x_k in V(G'_k)).

Wlog, assume (y in V(G'_1)). Then all vertices in (G'_2) have degree at least 3 in G. So in (G'_2), all vertices except possibly (x_2) have degree at least 3. Moreover, since (x_2 eq y), (x_2) has another neighbor except for (x_1) and (x_3) in G, therefore (V(G'_2) geq 2). So (G'_2) would be a smaller counterexample than G.

Remark: A closer examination of the proof reveals that in fact, it suffices to assume that all but at most two vertices satisfy (N(x) geq 3) with (V(G) geq 3) being required this time.