Math 240 Discrete Mathematics - Eulerian and Hamiltonian

Graph Theory

Proposition: (G) is a (connected) graph, (G) is Eulerian if and only if all vertices degrees are even

Proof: “(\rightarrow)“ Last class.

((\leftarrow)) Suppose all vertex degrees in (G) are even and (G) connected.

Idea: Start from any circuit, build longer circuits, end up with Eulerian circuit.

Lemma: If $ C = w_1, w_2, \dots, w_k = w_1$ is a circuit, and (C^\prime = w_i, x_1, x_2, \dots ,x_j,w_i) is a second circuit, then

$ \hat{C} = w_1, w_2,\dots, w_i, x_1, x_2, \x_j, w_i, w_{i+1}, \dots w_k$

.. figure:: |filename|/math240res/images/hamiltonianexample.png

So let (C = ebdfe) be any circuit in (G) that has no repeated edges

If (C) is Eulerian then (G) is Eulerian If (C) is not Eulerian, then since (G) is conneted there is some (v) in (V) (say (v=d)) that touches an edge not in (C). Ignoring (C), still an even number of edges touching every vertex. Let (C^\prime = dcgfed) be a circuit starting and ending at (V), using none of the same edges as (C) and using no edge twice.

We make $\hat C = ebdcgfedfe $.

Keep adding circuits using the lemma until we have an Eulerian circuit. This is not just a proof, but an efficient algorithm for finding Eulerian circuit.

Note: Messy here eh? I find it messy too, but I hardly find any other better way to explain it.

Hamiltonian Paths and Cycles

Definition

A Hamiltonian cycle in a graph (G=(V,E)) is a cycle (w_1,w_2,\dots,w_n,w_1) that passes through every vertex in (G).

It is NP-complete to determine whether a graph has a Hamiltonian Cycle.

Example: Petersen graph

.. image:: http://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1\_tiny.svg/200px-Petersen1\_tiny.svg.png

2 edges incident to each vertex must be used.

Some edge of inner star must be used, 2 edges between inner star, outer cycle must be used.

It’s impossible to get Hamiltonian Cylcle from Petersen graph.

Why:

Label the corresponding vertices on the pentagon and star by 0, 1, 2, 3, 4.

If a Hamiltonian cycle exists it must cross the bridge (between inner and outer loops) an even number of times, i.e. 2 or 4 times. Hence it must travel along the inner & outer loops 8 or 6 times.

Case 1: 8 times. The cycle must travel along the inner loop & outer loop 4 times each. It is easy to verify such a loop does not exist.

Case 2: 6 times. The cycle cannot travel on the outside/inside loop 5 times. So we must have 3 on the inside & 3 on the outside. Suppose we have 0-1-2 on the outer loop. Then bridge 1 is not used. So the remaining 4 bridges 0, 2, 3, 4 must be used. And the inner 1 is not adjacent to the outer 1, so we must have 4-1-3 on the inner loop. Having found 8 out of the 10 edges of the cycle, it is easy to verify that such a cycle does not exist.

Theorem (Dirac)

(G(V,E)) with (n) vertices, (G) is Hamiltonian if (n\geq3) and each vertex has degree $\geq{ n \over 2} $