For calculating number of edges in L(G), Refer ->
https://math.stackexchange.com/questions/301490/find-an-expression-for-the-number-of-edges-of-lg-in-terms-of-the-degrees-of
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.
line graph
http://mathworld.wolfram.com/LineGraph.html
for line graph we calculate in this way
i just follow this ...
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.
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-
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(d_{i,}2) =∑d_{i}(d_{i}−1) / 2 ,where i is vertex and d_{i} is degree of vertex i and n is the total no vertices in G.
Gatecse
OK @
In d link mentioned below. Yeah. :)