Distinguish edge traversal from vertex cycles

Try

An Euler circuit uses every edge once; a Hamilton cycle visits every vertex once before returning. The same graph can satisfy one property and fail the other. Two triangles sharing one vertex admit an Euler circuit, but a Hamilton cycle would have to pass through the shared vertex twice to visit both triangles. The objects being traversed—edges or vertices—determine the proof and algorithm.

Predict

Predict why degree parity characterizes Euler traversal but not Hamilton traversal. Every time an Euler trail enters an intermediate vertex, it must leave along a different unused edge, pairing incident edges. Only the two endpoints can have odd degree. Hamilton cycles merely select two edges at each vertex from a potentially larger graph, so the parity of the total degree is not the relevant condition.

Experiment

Compare three connected examples.

Graph	Euler circuit?	Hamilton cycle?
Cycle on six vertices	Yes	Yes
Two triangles sharing a vertex	Yes	No
Complete graph on four vertices	No	Yes

For the last graph every degree is three, so Euler parity fails. Write down a Hamilton cycle to show that the same odd degrees do not obstruct that property.

Understand

For Euler’s theorem, assume the vertices incident to edges form one connected component. If every degree is even, follow unused edges from any starting vertex until no further move is possible. Parity prevents termination at another vertex, so a closed trail results. If unused edges remain, connectedness provides a vertex on the existing trail incident to an unused edge. Build another closed trail there and splice it into the first. Each iteration consumes edges, so the finite procedure terminates with an Euler circuit. With exactly two odd vertices, add an auxiliary edge between them, construct a circuit, then remove that edge to obtain a trail. These arguments also provide an efficient traversal algorithm.

Apply

Dirac’s theorem gives a different sufficient condition: a simple graph on n≥3 vertices with minimum degree at least n/2 is Hamiltonian. Take a longest path v1,…, vk. Its endpoints have no neighbors outside the path. Among the k−1 indices, the sets where v1 meets v_(i+1) and where v_i meets vk have total size at least n≥k, so they overlap. This creates a cycle through all k path vertices by traversing one segment forward and the other backward. The degree bound also makes the graph connected, since every component would otherwise have more than n/2 vertices. If k< n, an edge from the cycle to an outside vertex yields a longer path, contradiction. Thus k=n and the cycle is Hamiltonian.

Continue

Dirac’s condition is sufficient, not necessary: a long cycle is Hamiltonian with minimum degree two. Failing the bound therefore gives no impossibility certificate. By contrast, a cut vertex in a graph with at least three vertices rules out a Hamilton cycle, since deleting any vertex from such a cycle leaves a connected spanning path. The introductory traversal lesson reviews terminology; here the new work is the constructive parity proof and the longest-path argument with its exact hypotheses.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with certify a maximum flow by a cut.