ACN Eulerian and Hamiltonian Graphs

Print preview

Handout 5.2 Eulerian and Hamiltonian Graphs

Let \(\bfG\) be a graph without isolated vertices. We say that \(\bfG\) is eulerian provided that there is a sequence \((x_0,x_1,x_2,\dots,x_t)\) of vertices from \(\bfG\text{,}\) with repetition allowed, so that

\(x_0=x_t\text{;}\)

🔗
for every \(i=0,1,\dots, t-1\text{,}\) \(x_ix_{i+1}\) is an edge of \(\bfG\text{;}\)

🔗
for every edge \(e\in E\text{,}\) there is a unique integer \(i\) with \(0\le i\lt t\) for which \(e=x_ix_{i+1}\text{.}\)

🔗

🔗

When \(\bfG\) is eulerian, a sequence satisfying these three conditions is called an eulerian circuit. A sequence of vertices \((x_0,x_1,\dots,x_t)\) is called a circuit when it satisfies only the first two of these conditions.

🔗

Theorem 5.6.

A graph \(\bfG\) is eulerian if and only if

🔗

Algorithm 5.7. Eulerian Circuit Finder.

Input 🔗: A graph \(\bfG=([n],E)\)
🔗
Output 🔗: An eulerian circuit \(C\) in \(\bfG\text{,}\) a vertex of odd degree in \(\bfG\text{,}\) or a connected component of \(\bfG\) and an edge of \(\bfG\) that is not in that connected component.
🔗

🔗

Initialize \(C=(1)\text{.}\)
🔗

🔗
While not every edge of \(\bfG\) is traversed, determine if any vertex of \(C\) is incident with an edge that has not been traversed.
1. If all vertices of \(C\) have all their edges traversed, then return the vertices of \(C\) as a connected component of \(\bfG\) with an edge not traversed by \(C\) demonstrating that \(\bfG\) is not connected.
  🔗
  
  🔗
2. If \(C\) has a vertex incident with an edge that has not been traversed, call that vertex \(u_0\text{.}\) Construct a walk \(W\) starting from \(u_0\text{.}\) From vertex \(u_i\text{,}\) follow the edge traversed by neither \(C\) nor \(W\) going to the neighbor of \(u_i\) with smallest label.
  🔗
  
  🔗
3. The construction of \(W\) halts at a vertex \(u_s\) for which all edges have been traversed.
  1. If \(u_s\neq u_0\text{,}\) then return \(u_0\) as a vertex of odd degree, showing that \(\bfG\) is not eulerian.
    🔗
    
    🔗
  2. If \(u_s = u_0\text{,}\) update the circuit \(C\) by replacing \(u_0\) in \(C\) with the walk \(W\text{.}\) Continue iterating by returning to step 2.
    🔗
    
    🔗
  🔗
  🔗
🔗
🔗
Return \(C\text{.}\)
🔗

🔗

🔗

Activity 5.2.1. Eulerian graphs.

(a)

Every group should have two pieces of paper. Each group must draw at least two graphs with \(n\geq 10\) vertices. Put your two graphs on separate pieces of paper.

One eulerian.
🔗

🔗
One not eulerian.
🔗

🔗
Label vertices with the integers from \(1\) to \(n\text{.}\)
🔗

🔗

🔗

(b)

Exchange graphs with another group.

🔗

(c)

Determine which graph is which.

🔗

(d)

Use our algorithm to find an eulerian circuit in the eulerian graph.

🔗

(e)

If finish early, draw some more graphs and swap with another group.

🔗

A graph \(\GVE\) is said to be hamiltonian if there exists a sequence \((x_1,x_2,\dots,x_n)\) so that

every vertex of \(\bfG\) appears exactly once in the sequence;

🔗
\(x_1x_n\) is an edge of \(\bfG\text{;}\) and

🔗
for each \(i=1,2,\dots,n-1\text{,}\) \(x_ix_{i+1}\) is an edge in \(\bfG\text{.}\)

🔗

Such a sequence of vertices is called a hamiltonian cycle.

🔗

Activity 5.2.2. Eulerian vs Hamiltonian.

(a)

Review responses on Canvas to class prep responses about difference between eulerian and hamiltonian.

🔗

(b)

Formulate an improved group explanation of the difference. Be careful in your use of the words circuit, cycle, and path.

🔗

Activity 5.2.3. Hamiltonian or Not?

The handout contains drawings of five graphs. Find a hamiltonian cycle or explain why there isn’t one. Don’t spend too much time on any one graph.

🔗

Peer instruction questions 1–5.

🔗

Theorem 5.8. Dirac’s Theorem.

If \(\bfG\) is a graph on \(n\geq 3\) vertices and each vertex in \(\bfG\) has at least \(\lceil \frac{n}{2}\rceil\) neighbors, then \(\bfG\) is hamiltonian.

🔗

Prev Top Next