Euler and Hamilton Paths and Circuits

<aside> 💡 Euler Path/Circuit - 遍历所有的边

Hamilton Paths/Circuits - 遍历所有节点

</aside>

Euler Circuit（只有偶点）

• A simple circuit that
  • contains every edge of a graph
  • start and end at the same vertex
• A graph $G$ has an Euler circuit if each vertex has even degree
• To find an Euler circuit:
  • Find a cycle and remove it from the graph
  • Repeat until the graph becomes empty
  • Merge these cycles at common vertices

Euler Path（两个奇点）

• A simple path that
  • contains every edge of a graph
  • doesn’t have to start & end at the same vertex
• A graph $G$ has an Euler path if it has
  • exactly two vertices of odd degree
  • if has 0 vertices of odd degree, the euler path = euler circuit
• To find an Euler path:
  • Add a dummy edge to join two odd-degree vertices
  • Find the Euler circuit
  • Remove the dummy edge, start at an odd-degree vertex

Hamilton Circuit

• A simple circuit that passes through every vertex of a graph
• NP-Complete problem

<aside> 💡 Ore’s Theorem

• let $G$ be a planar graph with $n\ge3$ vertices
• For all non-adjacent pairs of vertices $u,v$, $\deg(u)+\deg(v)\ge n$ </aside>

Hamilton Path

• A simple path that passes through every vertex of a graph
• No simple ways to test whether a graph has a Hamilton path
• NP-Complete problem

Planar Graphs