Question

Prove

i.) The line graph of P_n is P_n-1

ii.) The line graph of C_n is C_n

Answer 1

i) No. of edges in Pn is n. Hence L(Pn) has n-1 vertices.Name them 1,2,..,n-1. edges i and i+1 have common point hence in L(Pn) vertices i and i+1 are adjacent and so it is isomorphic to P(n-1)

ii) Consider a cycle with n vertices, it has n edges in its path. By these edges as vertices in L(Cn), we form a cycle with n edges. This implies that, both Cn and L(Cn) has same number of vertices and edges and also have the same degree sequence. So, there exists a 1-1 correspondence between V(Cn) into V(L(Cn)) and E(Cn) and E( L(Cn)) and preserves adjacency