Graph Theory Lessons

 Answers to Lesson 11

  1. Cn has n edges.

  2. The circuit C3 is the complete graph K3.

  3. The adjacency matrix for C6 is
    .

  4. The chromatic number of C7 is 3, the chromatic number of C8 is 2, and the chromatic number of C11 is 3

  5. In general, the chromatic number of Cn is 2 if n is even 3 and if n is odd.
  6. Cn is bipartite if n is even
  7. A bipartite graph cannot contain a circuit Cn with n odd as a subgraph because such a circuit has chromatic number 3 while a bipartite graph has chromatic number 2.

  8. The largest cycle that is a subgraph of the Petersen graph is C9.

  9. The largest cycle that is a subgraph of the Herchel graph is C10.
  10. Wn has one vertex of degree n - 1 and n - 1 vertices of degree 3. The sum of the degrees is therefore
    n - 1+3(n - 1) = 4n - 4.
    The number of egdes is half the sum of the degrees, i.e., 2n - 2.

  11. The wheel W4 is isomorphic to the complete graph K4.(We are assuming n > 3 so we don't count W1 to W3 )

  12. The adjacency matrix for W8 is

    .
  13. The chromatic number of Wn is 4 if n is even and 3 if is odd.

  14. A wheel can not be bipartite as its chromatic number is always greater than 2.
    15. e-mail: C. Mawata
    © C. Mawata