GATE CSE 2013 · Q26

MCQ2 marksMedium

Time00:00

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^{\prime}$ in $G$ , $L(G)$ has an edge between $v(e)$ and $v(e^{\prime})$ , if and only if $e$ and $e^{\prime}$ 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.

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: A) P only

Discrete Mathematics

Let us evaluate each statement:

(P) True: The line graph of any cycle $C_n$ ( $n \ge 3$ ) has $n$ vertices and $n$ edges forming a cycle isomorphic to $C_n$ .
(Q) False: Consider the complete graph $K_4$ , which has 6 edges. Its line graph $L(K_4)$ has 6 vertices and is 4-regular (the octahedron graph), which is not a clique ( $K_6$ ).
(R) False: Consider the planar star graph $K_{1,5}$ . Its line graph is the complete graph $K_5$ , which is non-planar by Kuratowski's theorem.
(S) False: The star graph $K_{1,3}$ is a tree, but its line graph $L(K_{1,3})$ is the complete graph $K_3$ (a triangle cycle), which is not a tree.

Therefore, only statement (P) is true, so (A) is the correct option.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Discrete Mathematics previous year question is Q26 of the GATE CSE 2013 paper. Find more GATE CSE PYQs on Discrete Mathematics in Engineering Mathematics, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Discrete Mathematics PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Discrete Mathematics in GATE CSE

Discrete Mathematics has 50 GATE CSE PYQs across 23 papers from 2011 to 2026. 11 of them are 2-mark MCQs like this one, and GATE CSE 2013 has 4.

How GATE tests Discrete Mathematics

More from GATE CSE 2013

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.