The line graph L(G) of a simple graph G is defined as follows: There is…
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.
Answer: A. P only — ConceptThe line graph L(G) turns each edge of G into a vertex, and joins two such vertices exactly when their edges share an endpoint in G. So a statement…
- A.
P only
- B.
P and R only
- C.
R only
- D.
P, Q and S only
Attempted by 35 students.
Show answer & explanation
Correct answer: A
Concept
The line graph L(G) turns each edge of G into a vertex, and joins two such vertices exactly when their edges share an endpoint in G. So a statement "L(G) is of type T whenever G is of type T" is FALSE the moment a single G of that type produces an L(G) outside T. One counterexample per claim settles it.
Testing each statement
(P) Cycle → cycle. A cycle Cn has n edges arranged in a ring; each edge shares an endpoint only with its two neighbours, so the n edge-vertices reconnect into a ring of length n. Thus L(Cn) = Cn. TRUE.
(Q) Clique → clique. In K4 the two edges {1,2} and {3,4} share no endpoint, so their edge-vertices are NOT adjacent in L(K4). Hence L(K4) is missing edges and is not complete (it is the octahedron). FALSE.
(R) Planar → planar. The star K1,5 is planar, but all 5 of its edges meet at the centre, so every pair of edge-vertices is adjacent: L(K1,5) = K5, which is non-planar. A planar G produced a non-planar L(G). FALSE.
(S) Tree → tree. The claw K1,3 is a tree, but its 3 edges pairwise share the centre, so L(K1,3) = K3 = C3, a triangle (a cycle, not a tree). FALSE.
Cross-check
Only (P) survives, and it survives for every n. (Q), (R) and (S) each fall to a single small graph, so exactly one statement is true.
Result
Only statement (P) is true.