Eulerian Graphs

• Read section 6.1, pages 133-139
• What is an Eulerian circuit in a graph? What is an Eulerian graph?
  • Do path-/cycle-/complete- graphs have Eulerian circuits?
  • Do complete bipartite graphs have Eulerian circuits?
• What is an Eulerian trail?
  • Give examples of graphs that have an Eulerian trail but no Eulerian circuit. Can you find a smallest possible example?
• Examine the Konigsberg bridges example as a graph.
  • Prove that if a graph has an Eulerian trail, then there are at most two vertices (start and end of the trail) that could possibly have an odd degree; all other vertices must have an even degree.
• Theorem 6.1: A nontrivial connected graph is Eulerian if and only if all its vertices have even degree.
  • For reverse direction: Consider a trail of maximum length. Show it must be a circuit. Show it has to contain all the edges.
• Corollary 6.2: A connected graph contains an Eulerian trail if and only if exactly two vertices have odd degree.
  • Add a new vertex and connect it to the endpoints/odd-degree vertices.
• When is the product of two graphs Eulerian?
• Practice Problems: 6.1, 6.2, 6.4, 6.5, 6.6
• Challenge: 6.3