If G = (V, E) is an undirected loop-free graph, the line graph of G, denoted L(G), is a graph with the set E as vertices, where we join two vertices e1, e2 in L(G) if and only if e1, e2 are adjacent edges in G.
(a) Find L(G) for each of the graphs in Fig. 11.99.
(b) Assuming that |V| = n and |E| = e, show that L(G) has e vertices and (1/2) ˆ‘vˆˆV deg(v)[deg(v)-1] = [(1/2) ˆ‘vˆˆV[deg(v)]2]

(c) Prove that if G has an Euler circuit, then L(G) has both an Euler circuit and a Hamilton cycle.
(d) If G = K4, examine L(G) to show that the converse of part (c) is false.
(e) Prove that if G has a Hamilton cycle, then so does L(G).
(f) Examine L(G) for the graph in Fig. 11.99(b) to show that the converse of part (e) is false.
(g) Verify that L(G) is nonplanar for G = K5 andG = K3,3.
(h) Give an example of a graph G, where G is planar but L(G) is not.

Transcribed Image Text:

Figure 11.99