GATE 2013 CS (CS1) – Question 36

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

The line graph L(G) has one vertex per edge of simple G, and joins vertices iff their G edges share an endpoint. Which are always true? P: A cycle’s line graph is a cycle. Q: A clique’s line graph is a clique. R: A planar graph’s line graph is planar. S: A tree’s line graph is a tree.

P only
P and R only
R only
P,Q,S only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) P only

Explanation

P holds because every cycle edge touches its two neighbours. Q fails for K₄ because disjoint edges become nonadjacent line-graph vertices. R fails for planar star K₁,₅, whose line graph is nonplanar K₅. S fails for K₁,₃, whose line graph is a triangle. Thus only P, A.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

GATE 2011 CS (CS1) Q27 – The drawings show complete graph K₄ and cube graph Q₃. Which is true?
GATE 2010 CS (CS1) Q11 – For graph G=(V,E), let (G)= di dd, where i d counts vertices of degree d. If different…
GATE 2010 CS (CS1) Q38 – Which sequences cannot be degree sequences of simple graphs? I: 7,6,5,4,4,3,2,1 II:…
GATE 2015 CS (CS2) Q61 – A self-complementary graph is isomorphic to its complement. What must its vertex count n…
GATE 2015 CS (CS2) Q62 – A bridge is an edge whose removal disconnects a connected graph. Which is true?
GATE 2026 CS (CS1) Q55 – An undirected, unweighted, simple graph G(V, E) is said to be 2-colorable if there exists…

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →