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
GATE 2013 · Discrete Mathematics · Graph Connectivity · medium
Answer: A. P only
- Check P: L(cycle) is a cycle: In C_n, every edge is incident with exactly 2 other edges (one on each side). So each vertex of L(C_n) has degree 2, and L(C_n) is connected — hence L(C_n) = C_n. P is TRUE.
- Check Q: L(clique) is a clique: In K_4, edges {1,2} and {3,4} share no vertex, so they are NOT adjacent in L(K_4). Hence L(K_4) is not K_6. Q is FALSE (for n >= 4).
- Check R: L(planar graph) is planar: K_4 is planar, but L(K_4) = K_{1,1,1,1,1,1} (octahedron graph), which is planar. However K_5 is planar and L(K_5) contains K_5 as minor and is non-planar. So R is FALSE.
- Check S: L(tree) is a tree: Star K_{1,3} is a tree with 3 edges. L(K_{1,3}) has 3 vertices (one per edge) all pairwise adjacent (all share the center vertex) = K_3, which is a cycle — not a tree. S is FALSE.