Graph Theory Lessons

Answers to Lesson 16

  1. If a graph G is regular of degree r, then Prism(G) is regular of degree r + 1.

  2. If a graph G has an Euler circuit then it is connected and all its vertices have even degree. However, by problem 1, this means that all the vertices in Prism(G) have odd degree so Prism(G) does not have an Euler circuit.

  3. Of the n-cubes available in the program, the 2-cube, 4-cube, and 6-cube have Euler circuits.

  4. Yes. To show that Prism(G) can be properly colored with 2 colors , first color G properly with 2 colors(say black and white). This can be done since G is bipartite. Now when you form Prism(G), for each vertex v that is white, color the corresponding vertex black and if v is colored black then color the corresponding vertex white. This will give you a 2-coloring of Prism(G). Therefore Prism(G) is bipartite. As an example, below is a coloring of the prism of a bipartite graph:

  5. Using the previous result and the fact that the n-cube is Prism(n-1 cube) we can prove by induction that all the n-cubes are bipartite.

  6. The chromatic number of Prism(N(3)) is 2. If X(G) = 1 then X(Prism(G)) = 2.

  7. If X(G = c where c > 1 then X(Prism(G)) = c.

  8. From the answer to the previous problem, X(Prism(Kn) = n if n > 1, and X(Prism(K1) = 1.

  9. If a graph G has a Hamilton circuit

    then using vi' to represent the vertex corresponding to vi we have a Hamilton circuit in Prism(G) that goes

e-mail: C. Mawata
© C. Mawata