GATE 2013 · session-1
The line graph L(G) of a simple graph G is defined as follows:
• There is exactly one vertex v(e) in L(G) for each edge e in G.
• For any two edges e and e′ in G, L(G) has an edge between v(e) and v(e′) if and only if e and e′ are incident with the same vertex in G.
Which of the following statements is/are TRUE?
(P) The line graph of a cycle is a cycle.
(Q) The line graph of a clique is a clique.
(R) The line graph of a planar graph is planar.
(S) The line graph of a tree is a tree.