Line Graph Doubt

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?

1. The line graph of a cycle is a cycle.
2. The line graph of a clique is a clique.
3. The line graph of a planar graph is planar.
4. The line graph of a tree is a tree.

I have already done the following:

1. The line graph of a cycle is a cycle.

2. [See below.]

3. The line graph of a planar graph is planar. Proof by counter-example: Let $$G$$ have $$5$$ vertices and $$9$$ edges which is a planar graph but $$L(G)$$ isn't a planar graph because then it will have $$25$$ edges; therefore, $$|E|\leq 3\cdot|V|-6$$ is violated.

4. The line graph of a tree is a tree. By counter-example: Try drawing a simple tree which has a root node. The root node has one child $$A$$ and node $$A$$ has two children $$B$$ and $$C$$. Draw its line graph according to given rules in question and you will get a cycle graph of $$3$$ vertices.

My doubt is that I can't figure out 2. The line graph of a clique is a clique. Please help me out here.

• In your example for (R) are you sure $L(G)$ has $25$ edges? I only count $24$ (which is enough). Anyway isn't the star graph $K_{1,5}$ a simpler example? The line graph is $K_5$ which is not planar. As for (Q) what is the line graph of $K_4$? Can't you find two edges in $K_4$ which have no common vertex? – bof Aug 19 '19 at 6:47
• Yes it will have 25 edges using this formula math.stackexchange.com/questions/301490/… – John Lucas Aug 19 '19 at 6:49
• The line graph of a clique will be a clique iff every two edges of the clique are adjacent. Are they? – Matthew Daly Aug 19 '19 at 7:02
• @JohnLucas According to that formula the number of edges in $L(G)$ is $$\frac{4\cdot3}2+\frac{4\cdot3}2+\frac{4\cdot3}2+\frac{3\cdot2}2+\frac{3\cdot2}2=6+6+6+3+3=24.$$ – bof Aug 19 '19 at 7:33
• @JohnLucas There is no such graph. Did you try to draw it? If there are $5$ vertices, each vertex of degree $4$ must be joined to all the other vertices, including your supposed vertex of degree $2$. No, there is (up to isomorphism) only one (simple) graph with $5$ vertices and $9$ edges; it's the graph you get by removing one edge from the clique $K_5$; its degree sequence is $4,4,4,3.3$ (the endpoints of the missing edge lose one degree); and its line graph has $24$ edges. – bof Aug 20 '19 at 9:26

HINT: Let $$G$$ be a clique on the $$n$$ vertices $$\{x_1,x_2,\ldots, x_n\}$$ for $$n \ge 4$$. Then edges $$e_1 = x_1x_2$$ and $$e_2=x_3x_4$$ do not share a vertex. So are $$v(e_1)$$ and $$v(e_2)$$ adjacent to each other in $$L(G)$$?
If you want to look at this another way, $$L(K_n)$$ has $$\frac{n(n-1)}{2}$$ vertices. But for each $$e \in K_n$$, the vertex $$v(e)$$ has degree only $$2(n-2)$$ [make sure you see why]. Note that $$\frac{n(n-1)}{2} - 1$$ $$>>$$ $$2(n-2)$$ for $$n > 6$$.