3 Prove that K3 and K13 have isomorphic line graphs but are

3. Prove that K3 and K1,3 have isomorphic line graphs but are not isomorphic to each other.

Solution

The line graph L(G) of a simple graph G is the graph whose vertices are in one-to-one correspondence with the edges of G, two vertices of L(G) being adjacent if and only if the corresponding edges of G are adjacent.

K3 and K1,3 both contain 3 edges and all the edges are adjacent at at least one vertex, so we have that both L(K3) and L(K1,3)(line graph) are isomorphic to K3, but are not isomerphic to each other.