May 1st

Eulerian Circuits


Useful facts

The problems

  1. Find a connected graph with as few vertices as possible that has precisely two vertices of even degree.
  2. Prove that a graph is bipartite if and only if it contains no odd cycles
  3. Take two Eulerian graphs that share no vertices and connect them with a single edge. Is the resulting graph Eulerian? Does the resulting graph contain an Eulerian trail?
  4. For any distinct vertices, \(u\) and \(v\) in a graph, prove that there is a walk between \(u\) and \(v\) if and only if there is a path from \(u\) to \(v\)
  5. Is the following graph Eulerian? If so find an Eulerian circuit.
  6. Here is a five room house, try to draw any continuous line that crosses every wall exactly one time. What can you prove and how? Here is a sample line:

    "WallsLines2". Licensed under CC BY-SA 3.0 via Wikipedia.

  7. (Next daily challenge) Research question: prove that the Petersen graph is not Hamiltonian