Graph Theory Lessons

Answers to Lesson 15

  1. The complement of the complete graph Kn is the null graph Nn.

  2. The complement of Kr,s is Kr U Ks.

  3. The complement of the complete tripartite graph Kr,s,t is Kr U Ks U Kt.

  4. Consider a vertex v in the graph. Since the graph is regular of degree r, the vertex v is adjacent to r vertices. In the complement, v will be not be adjacent to those vertices but instead to all the other n - 1 - r vertices. So the complement is regular of degree n - 1 - r.

  5. We know that Cn is regular of degree 2 so if it is isomorpic to its complement the complement must also be regular of degree 2. The previous problem tells us that this can only happen if n - 1 - r = 2 with r = 2. Therefore must be n = 5. We check and find that C5 is indeed isomorphic to its complement.

  6. The complement of the star Sn is Kn - 1 U N1.

  7. The complement of the Petersen graph does have an Euler circuit.

  8. The key to this problem is that if a vertex has degree d in G then it has degree n - 1 - d in ~G. Suppose a graph G on n vertices, n odd, has an Euler circuit. Since G has an Euler circuit we know that every vertex in G has even degree. Now note that if a vertex v has even degree d in G then it has degree n - 1 - d in ~G. Since n is odd, the number n - 1 - d will be even. Therefore all the vertices in ~G have even degree. If ~G is connected, it will have an Euler circuit.

  9. The same argument as in the previous problem tells us that the graph ~G will not have an Euler circuit.

  10. ~C5 U ~S7 is isomorphic to ~(C5 + S7).

  11. ~G1 U ~G2 is isomorphic to ~(G1+G2).
e-mail: C. Mawata © C. Mawata