The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+6 votes


  1. the line graph for a complete graph is complete
  2. the line graph for a connected graph is connected
  3. the line graph for a bipartite graph is bipartite 
asked in Graph Theory by Veteran (98.5k points)
retagged by | 323 views
Option B). is true.
yes, Agreed. (y)
why not option C?

2 Answers

+6 votes

option B is the right answer

We can solve this question by eliminating options

Option (A) False

Let us take a complete graph of  $4$ vertices:

In a line graph, no. of edges is

$\sum_{i=0}^{n}$  ${}^{d_{i}}C_{{2}},$     $d_{i}$is degree of each vertex

=$\frac{3\times 2}{2}+\frac{3\times 2}{2}+\frac{3\times 2}{2}+\frac{3\times 2}{2} = 3\times 4=12$

No. of vertices in line graph = No. of edges in original graph
No. of vertices in line graph $= 6$
So, no. of edges to make complete graph with $6$ vertices $= \frac{6\times 5}{2} = 3\times 5=15$
But for given line graph from complete graph of $4$ vertices we have only $12$ edges.

Option (B)   True

1. Smallest line graph for original graph one edge

     which is also connected graph

If a graph is connected with more then one edge, it will never be disconnected 

Option (C)    False

This cannot be 2-colorable and hence is not bipartite. 

Option (D)    False

Because line graph degree of vertex depends on the attribute

e.g., $\left [ A,B \right ]$ as point in line graph, then degree of this vertex depends on degree of $A$ and degree of $B$ in the original graph.

I'm drawing degree for a point $[AB]$ in line graph.

So, this is wrong.

Option (E)    False (wrong as proved in above option (D))

answered by Active (4.8k points)
edited by
+2 votes


We can also do this question using elimination of options. 

You can view the following google drive link for the example -

answered by Active (1.5k points)
edited by

I have corrected the example, and updated the file.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,194 questions
43,647 answers
42,929 users