Graph Theory Lessons

Answers to Lesson 12

  1. The complete graphs Kn with n odd have Euler circuits.

  2. The octahedron is the only platonic graph that has an Euler circuit.

  3. A complete bipartite graph Kr,s has an Euler circuit if r and s are both even.

  4. A complete tripartite graph Kr,s,t has an Euler circuit if r, s, and t are all even or all odd.

  5. The Petersen graph does not have an Euler circuit.

  6. An example of a simple graph with all vertices of even degree but no Euler circuit is
    .

  7. All the complete graphs Kn with n > 2 have Hamilton circuits.

  8. All the platonic graphs have Hamilton circuits.

  9. The complete bipartite graph Kr,s has a Hamilton circuit if and only if r = s.

  10. The cubes, Q2 and Q4 have Euler circuits. Actually the n-cubes with n even all have Euler circuits but if you try the 6-cube you will probably crash the program as there are so many vertices and edges.

  11. All n-cubes, n=2,3,4,5 have Hamilton circuits.
  12. All n-cubes, n=2,3,4,5 are bipartite.
e-mail: C. Mawata
© C. Mawata