Let G be a graph. The line graph of G is a new graph L.G/ whose vertices are the edges

Chapter 51, Problem 51.9

(choose chapter or problem)

Let G be a graph. The line graph of G is a new graph L.G/ whose vertices are the edges of G; two vertices of L.G/ are adjacent if, as edges of G, they share a common end point. In symbols: V L.G/ D E.G/ and EL.G/ D fe1e2 W je1 \ e2j D 1g : Prove or disprove the following statements about the relationship between a graph G and its line graph L.G/: a. If G is Eulerian, the L.G/ is also Eulerian. b. If G has a Hamiltonian cycle, then L.G/ is Eulerian. (See Exercise 50.16 for the definition of a Hamiltonian cycle.) c. If L.G/ is Eulerian, then G is also Eulerian. d. If L.G/ is Eulerian, then G has a Hamiltonian cycle.