edited by
18,870 views
59 votes
59 votes

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.
     
  1. $P$ only
  2. $P$ and $R$ only
  3. $R$ only
  4. $P, Q$ and $S$ only
edited by

8 Answers

1 votes
1 votes

Everything you need to know about LINE GRAPHS

 

You won’t find anything better than this anywhere as its from NPTEL IIT MADRAS.

 

0 votes
0 votes

P is correct “The line graph of a cycle is a cycle.”

Q is incorrect

R can be verified from the CUBE graph. The CUBE graph is planar but its line graph isn’t. (no need to fully make its line graph. In midway only we can conclude it)

S is incorrect.

hence option A is correct answer

0 votes
0 votes

Option A is true.

Let us take a K4. It is both complete and planar.

How many vertices does a complete graph have? - Quora

Its linear graph will be a square pyramid which is neither complete nor planar.

Square pyramid - Wikipedia

So, both Q and R is false.

Let us take a 7 vertex binary tree.

The linear graph of this tree will be 

 

 

 

 

 

So, S is also false.

Now for S, let us take a C6.

Hexagon – Definition, Shape, Properties, Formulas

The linear graph of C6 will be

File:Regular hexagon.svg - Wikimedia Commons

So, only P is true.

Answer:

Related questions

25 votes
25 votes
2 answers
1
Arjun asked Sep 24, 2014
15,923 views
Which of the following statements is/are TRUE for undirected graphs?P: Number of odd degree vertices is even.Q: Sum of degrees of all vertices is even. P only Q only Both...
3 votes
3 votes
0 answers
2
dd asked Nov 22, 2016
5,266 views
For which values of n are these graphs bipartite ?1. $K_n$2. $C_n$3. $W_n$4. $Q_n$
43 votes
43 votes
8 answers
3
32 votes
32 votes
9 answers
4
makhdoom ghaya asked Feb 13, 2015
24,385 views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.