Question

Dirac's Theorem states that "A simple graph with n vertices (n >= 3) is Hamiltonian if every vertex has degree n / 2 or greater". Show that K n,n is Hamiltonian for all n >= 3

Answer 1

Proof:

Let P=p1p2…pkP=p1p2…pk be the longest path in GG.

If p1p1 is adjacent to some vertex vv not in PP, then the path vp1p2…pkvp1p2…pk would be longer than PP, contradicting the choice of PP.

The same argument can be made for pkpk.

So both p1p1 and pkpk are adjacent only to vertices in PP.

Since deg(p1)≥n2deg⁡(p1)≥n2 and p1p1 cannot be adjacent to itself, k≥n2+1k≥n2+1.

Claim: There is some value of jj (1≤j≤k1≤j≤k) such that:

• pjpj is adjacent to pkpk, and
• pj+1pj+1 is adjacent to p1p1.

Suppose that the claim is not true.

Then since all vertices adjacent to p1p1 or pkpk lie on PP, there must be at least deg(p1)deg⁡(p1) vertices on PP not adjacent to pkpk.

Since all the vertices adjacent to pkpk and pkpk itself also lie on PP, the path must have at least deg(p1)+deg(pk)+1≥n+1deg⁡(p1)+deg⁡(pk)+1≥n+1 vertices.

But GG has only nn vertices: a contradiction.

This gives a cycle C=pj+1pj+2…pkpjpj−1…p2p1pj+1C=pj+1pj+2…pkpjpj−1…p2p1pj+1.

Suppose G−CG−C is nonempty.

Then since GG is connected, there must be a vertex v∈G−Cv∈G−C adjacent to some pipi.

So the path from vv to pipi and then around CC to the vertex adjacent to pipi is longer than PP, contradicting the definition of PP.

Therefore all vertices in GG are contained in CC, making CC a Hamilton cycle.