Question

3. Find the number of vertices and edges for the line graph L(G) of a graph G with the degree sequence (di, d2, , dp). (Note that all edges in G incident to the same vertex are pairwise adjacent in L(G).)

Answer 1

Let G be the graph without loss of generality suppose G is simple Definition: line graph of g L(G): It is a graph obtained by treating edges of G as a vertices of L(G) and two vertices of L(G) are adjacent if and if their corresponding edges (are incident on) shares common end points In simple words, L(G) is obtained from G by considering edges of G as a vertices of L(G) and vertices of G as an edges of L(G) Example: consider G as rightarrow no.of vertices in G = 5 no.of edges in G = 6 then L(G) is no.of vertices in L(G) = 6 no.of edges = 9 degree sequence of G is 2, 2, 2, 3, 3, and degree sequence of L(G) is 2, 3, 3, 3, 3,4 Remark if G is graph with n-vertices and m-edges then no.of vertices is L(G) is M no.of edges is half the sum of the sequence of the degree