# GATE CSE 2013 | Question: 26

10.3k views

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
4

Cycle: Line graph of a cycle is the cycle: $\checkmark$(Observe on this) Tree: Line graph of a tree is the tree: $\times$ (Observe on this) Planar: Line graph of a planar graph is planar: $\times$

https://math.stackexchange.com/questions/1588035/planar-graph-whose-line-graph-is-non-planar

Clique: Line graph of a clique is clique: $\times$ (Observe on this) 0
what is the problem with the given planar graph ?

isn't it's line graph is planar ?
1

This graph is the graph which is told in words in below answer 0

Line graph

0
Please someone explain @chotu link content. I am not able to understand how it can be used.

P) True. Because every edge in cycle graph will become a vertex in new graph $L(G)$ and every vertex of cycle graph will become an edge in new graph.

R) False. We can give counter example. Let $G$ has $5$ vertices and $9$ edges which is a planar graph. Assume degree of one vertex is $2$ and of all others are $4$. Now,  $L(G)$ has $9$ vertices (because $G$ has $9$ edges ) and $25$ edges. (See below). But for a graph to be planar $|E| <= 3|V| - 6$.

For $9$ vertices $|E| \leq 3*9 - 6$

$⇒|E| \leq 27 - 6$

$⇒|E| \leq 21$. But $L(G)$ has $25$ edges and so is not planar.

As R) is False option (B), (C) are eliminated.
http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/planarity.htm

S) False. By counter example. Try drawing a simple tree which has a Root node ,Root node has one child A, node A has two child B and C. Draw its Line graph acc. to given rules in question you will get a cycle graph of $3$ vertices.

So (D) also not correct.

$\therefore$  option (A) is correct.

For a graph G with n vertices and m edges, the number of vertices of the line graph L(G) is m, and the number of edges of L(G) is half the sum of the squares of the degrees of the vertices in G, minus m.

edited by
0
and every vertex of cycle graph will become an edge in new graph ???
0
yes. You can easily verify rt?
0
how edges becomes 24 in R case(planar graph)
1
Can you please explain how line graph with 9 vertices has 24 edges?
0
24 edge(add degree of each vertices and divided by 2 ie. 48/2)
some one explain above that how 24 edges ??
0
That was wrong statement :O
1 no of vertices= 11 as no of edges

but no of edges = 1/2(62+22+32+32+32+32+22)= 80/2=40

e>3v-6 for not to be planar

40>3*11-6

40 >33-6 =27 so  line graph of planar graph need not to be planar. is this is true?

22 There is very simple and easy proof to drive expression for number of edges in lines graph-

$L(G)$ is a $2$-set $\{e_1,e_2\}$ of edges in $G$ with which are adjacent to a common vertex $v$. This vertex $v$ is uniquely determined by $\{e_1,e_2\}$.
If a vertex $v$ has degree $d$, there are $\binom{d}{2}$ $2$-sets $\{e_1,e_2\}$ such that $e_1$ and $e_2$ are adjacent to $v$

So the total number of edges in $L(G)$ is
$$\sum_{i = 1}^n \binom{d_i}{2} = \sum_{i = 1}^n \frac{d_i(d_i-1)}{2}\text{.}$$
Ref: http://math.stackexchange.com/questions/301490/find-an-expression-for-the-number-of-edges-of-lg-in-terms-of-the-degrees-of

0
@Arjun sir ,  plz explain above solution?? i am not get this line

Assume degree of one vertex is 2 and of all others are 4 we take L(G) has 9 vertices (because G has 9 edges )
0
@arjun sir

please give diagram of counter example of statement R.
0
Sir is Q also correct?
0
0
L(G) in this example has 24 edges. Please fix it.
0
How  are we finding number of edges in L(g) in R statement?How is it 25 .Please explain.Not getting it.
1
V= 5 , e=9 in original graph now in line graph vertex=9 and edges will be ,given 1 vertex has 2 degree and other 4 has 4 degree so 2^2+4*(4^2)= 68 ,68/2= 34,

34- 9=25 ,
0
In total there are 5 vertices.So 1*2+4*4=18. Where is ^2 coming from?Can you tell that?I am missing in this particular option:(.

Please elaborate a bit on the last calculation of getting 34 and 25?
1

for line graph we calculate in this way

For a graph G with n vertices and m edges, the number of vertices of the line graph L(G) is m, and the number of edges of L(G) is half the sum of the squares of the degrees of the vertices in G, minus m.

0
OK.so is this some property of line graph?
1
yes , and sachin metioned some method that could also used
0
GOt it.Thanks :)
0

V= 5 , e=9 in original graph now in line graph vertex=9 and edges will be ,given 1 vertex has 2 degree and other 4 has 4 degree so 2^2+4*(4^2)= 68 ,68/2= 34,

34- 9=25

Can somebody draw a graph for this ?  This selected answer should also tell how the the number of edges is 25 in the line graph along with the diagram. I am unable to get it.

0
nice explanation
0
Q is true? I have tried it and i am getting it true.

Can anyone verify if Q is also coming true?

Although ans is (A) only but i need to verify if i am doing all right.
0

@Shaik Masthan comment by sachin sir is very important to get intuition for this problem rather than rote learning which is given in second part of the answer. I think sachin sir comment should be included in answer for better understanding.

2
0
thinking of a  counter example for statement R is commendable!! L(G) is a 2-set {e1,e2} of edges in G with which are adjacent to a common vertex v. This vertex v is uniquely determined by {e1,e2}.

If a vertex vv has degree d, there are (d2) 2-sets{e1,e2} such that e1 and e2 are adjacent to v

So the total number of edges in L(G) is

$\sum_{i=0}^{n}\binom{n}{2}=n(n-1)/2$

There is very simple and easy proof to drive expression for number of edges in lines graph-   edited
1
perfect saket :)
0
@Saket, Sir how u have found number of edges in line graph? Which formula u r using?
0

Just small correction

Formula for finding no of edges in L(G):

If a vertex v has degree d, there are C(d,2) 2-sets {e1,e2} such that e1 and e2 are adjacent to v
So the total number of edges in L(G) is

From i=1 to n ,∑C(di,2) =∑di(di−1) / 2 ,where i is vertex and di is degree of vertex i and n is the total no vertices in G.

1
last calculation is having some mistake,

no. of edges = $\frac{4*3}{2} + \frac{3*2}{2} + \frac{4*3}{2} + \frac{3*2}{2} + \frac{4*3}{2}$ =  6 + 3 +6 +3 +6 =24

Everything you need to know about LINE GRAPHS         You won’t find anything better than this anywhere as its from NPTEL IIT MADRAS.

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

## Related questions

1
10.3k 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 P and Q Neither P nor Q
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $n-k$ $n-k+1$