The line graph \(L(G)\) of a simple graph \(G\) is defined as follows: • There…
2013
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.
- A.
P only
- B.
P and R only
- C.
R only
- D.
P, Q and S only
Attempted by 104 students.
Show answer & explanation
Correct answer: A
Answer: Only the statement that the line graph of a cycle is a cycle is true.
P (The line graph of a cycle is a cycle): True. If G is a cycle Cn, each edge of Cn is incident with exactly two other edges (its neighbours along the cycle). In L(G) each corresponding vertex therefore has degree 2, and the adjacency order is the same cyclic order, so L(G) is a cycle of length n.
Q (The line graph of a clique is a clique): False in general. For small cliques like K2 and K3 the line graph is trivial or K3 respectively, but for K4 there exist two edges that are disjoint (they do not share a vertex), so their corresponding vertices in the line graph are not adjacent. Thus L(K4) is not complete.
R (The line graph of a planar graph is planar): False. A simple counterexample is the star graph with five leaves (the tree K1,5), which is planar. Its line graph is K5 (because all five edges are pairwise incident at the center), and K5 is nonplanar. Therefore planarity need not be preserved by the line graph operation.
S (The line graph of a tree is a tree): False in general. If a tree has a vertex of degree d≥3, the d edges incident at that vertex form a clique Kd in the line graph; for d=3 this already gives a triangle, so the line graph contains a cycle and is not a tree. Only trees that are paths have line graphs that are trees (a path on n vertices gives a path on n−1 vertices).
Final conclusion: Only the statement about cycles is always true, so the correct answer is the choice that states only P is true.