Weird, wild stuff: prove that a 3-regular graph must have a cycle of even length

Question

Weird, wild stuff: prove that a 3-regular graph must have a cycle of even length. This seems crazy difficult, since we don't know what our 3-regular graph looks like. It could be reeeeeeeeeeeeeallllllly complicated. So, there's no point in trying to draw a 3-regular graph here. We need some kind of clever proof attack. Remember when we proved a tree always has to have a leaf, and I said I would torture you that with a problem that used the same proof technique? Remember that proof, where we started out with a longest path? Do that here. When you draw your longest path and what not, you will be staring at a few cycles. Now, we want to prove that there is a cycle of even length in our graph; one of the cycles you're looking at definitely has even length. But why? You'll need to consider some kind of cases.

Explanation / Answer

simple finite graphs. (An infinite cubic graph need not contain any cycles at all; a "loopy" cubic graph need not contain any cycle of length greater than one; a graph with parallel edges contains cycles of length two.)

Yes, every cubic (3-regular) graph contains an even cycle. It will suffice to show that the graph contains a "theta" subgraph, i.e., two distinct vertices connected by three internally disjoint paths. Two of the th ree paths will have lengths of the same parity, so their union will be the desired even cycle.

Let G be a cubic graph. Without loss of generality, we may assume that G is connected. Let v be a vertex of G which is not a cut-vertex, i.e., Gv is connected. (E.g., any vertex of maximum eccentricity is not a cut-vertex.) The vertex v is adjacent to 3 distinct vertices x,y,z of Gv.

Since Gvis connected, x is connected to y by a path x0,x1,…,xm in Gv, with x0=x and xm=y. Now let z0,z1,…,zn be a path of minimum length in Gv connecting z to {x0,x1,…,xm}, with z0=z and zn=xj. Now it's easy to see that xj is connected to v by three internally disjoint paths in G, one through each of the vertices x,y,z

.we don't need regularity; the same argument works for any graph with minimum degree at least 3

.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.