Graph Theory Lessons

Answers to Lesson 18

  1. The circuit C3 and the star S4 are not isomorphic but L(C3) and L(S4) are isomorphic.

  2. A circuit graph Cn is isomorphic to its line graph.

  3. If an edge has a vertex of degree d1 at one end and a vertex of degree d2 at the other, the degree of its corresponding vertex in the line graph is d1 + d2 - 2

  4. From the answer to the previous question, if a graph G is regular of degree r then L(G) is regular graph of degree 2r - 2.

  5. From problem 4, if a graph G is regular, then every vertex of L(G) has even degree so if it is connected it had an Euler circuit.

  6. L(K5) has 10 vertices (the same number of vertices as the number of edges in K5). It is regular of degree 2*6 - 2 = 10, so the sum of the degrees of the vertices is 10 * 6 = 60 and it has 60/2 = 30 edges.

  7. L(L(K5))has 30 vertices (the same number of vertices as the number of edges in L(K5)). Since L(K5) is regular of degree 6, L(L(K5)) is regular of degree 2*6 - 2 = 10, so the sum of the degrees of the vertices is 30 * 10 = 300 and it has 300/2=150 edges.

  8. L(L(L(K5))) has 150 vertices. It is regular of degree 2*10 - 2 = 18, so the sum of the degrees of the vertices is 150*18 = 2700 and it has 2700/2=1350 edges.

  9. L(Sn) is Kn - 1.

  10. If a graph G contains a vertex of degree d then it has a subgraph isomorphic to Sd + 1 (the vertex of degree d together with the vertices adjacent to it). Therefore L(G) has a subgraph isomorphic to L(Sd + 1 ) = Kd. The chromatic number of Kd is d so the chromatic number of L(G) is greater than or equal to d.

  11. If the sum of the degrees of a graph is 16 then G has 16/2 = 8 edges. Its line graph will have 8 vertices.

  12. If the sum of the degrees of a graph is s then its line graph has s/2 vertices

  13. The octahedron is isomorphic to L(K4).
e-mail: C. Mawata
© C. Mawata