GATE CSE
First time here? Checkout the FAQ!
x
+14 votes
1.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.

(A) P only

(B) P and R only

(C) R only

(D) P, Q and S only
asked in Graph Theory by Veteran (294k points)  
edited by | 1.3k views

2 Answers

+20 votes
Best answer

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| <= 3*9 - 6

⇒|E| <= 27 - 6

⇒|E| <= 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.

∴ 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.

answered by (475 points)  
edited by
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?

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.

i just follow this ... 

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

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- 

 

answered by Loyal (4k points)  
edited by


Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2064 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,647 answers
79,695 comments
31,069 users