GATE CS 2013 Q26 — Graphs: Connectivity, Matching, Colouring

To determine which statements are true, let us analyze each one with definitions and counterexamples:

• Statement (P): The line graph of a cycle is a cycle.
  Let $G = C_n$ ($n \ge 3$) be a cycle. Each edge in $C_n$ is incident to exactly two other edges (one at each endpoint). In the line graph $L(C_n)$, each vertex represents an edge of $C_n$ and has a degree of exactly $2$. Since $C_n$ is connected, $L(C_n)$ is also connected and forms a cycle of length $n$ ($L(C_n) \cong C_n$).
  Thus, (P) is TRUE.


• Statement (Q): The line graph of a clique is a clique.
  Let $G = K_4$ (a clique of size 4). Consider two independent (disjoint) edges in $K_4$, such as $e_1 = (1, 2)$ and $e_2 = (3, 4)$. Since $e_1$ and $e_2$ do not share any vertex, their corresponding vertices in $L(K_4)$ are not connected by an edge. Thus, $L(K_4)$ is not a complete graph (clique).
  Thus, (Q) is FALSE.


• Statement (R): The line graph of a planar graph is planar.
  Let $G = K_{1,5}$ (a star graph with $5$ leaves), which is a tree and therefore planar. All $5$ edges of $K_{1,5}$ share the single central vertex, meaning every pair of edges is mutually incident. Consequently, the line graph $L(K_{1,5})$ is the complete graph $K_5$. By Kuratowski's Theorem, $K_5$ is non-planar.
  Thus, (R) is FALSE.


• Statement (S): The line graph of a tree is a tree.
  Let $G = K_{1,3}$ (a star graph with $3$ leaves), which is a tree. Since all $3$ edges share the central vertex, they are mutually incident. The line graph $L(K_{1,3})$ is $K_3$ (a cycle of length 3), which contains a cycle and is therefore not a tree.
  Thus, (S) is FALSE.

Therefore, only statement P is TRUE.