LG is the line graph of G Proof whether the following is tru

L(G) is the line graph of G. Proof whether the following is true (or false) for every graph G:

(a) G is connected if and only if L(G) is connected.

(b) G is Eulerian if and only if L(G) has a Hamiltonian cycle.

Solution

a).TRUE

The line graph of a connected graph is connected. If G is connected, it contains a path connecting any two of its edges, which translates into a path in L(G) containing any two of the vertices of L(G). However, a graph G that has some isolated vertices, and is therefore disconnected, may nevertheless have a connected line graph.

b).TRUE

Consider an Euler tour P of G. Hence every edge of G occurs exactly once in P. Consider the sequence S of vertices in L(G) corresponding to the edges in P. Then, every vertex of L(G) occurs exactly once in S. Also, for any two consecutive vertices u, v in S, the corresponding edges in G must have a common endpoint (or the Euler tour could not have them in sequence. Hence (u, v) E(L(G)). Hence S is a Hamiltonian cycle.