Line Graph Doubt

Question

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.

Answer 1

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$.

Answer 2

Let $K_{n}=(V(K_{n}),E(K_{n}))$ be a complete graph of $n$ vertices, then $|E(K_{n})|=\dfrac{n(n-1)}{2}$, and $|V(L(K_{n}))|=|E(K_{n})|=\dfrac{n(n-1)}{2}$.

$L(K_{n})$ is a complete graph (clique) if and only if $|E(L(K_{n}))|=\dfrac{|V(L(K_{n}))|(|V(L(K_{n}))|-1)}{2}$.

To count the number of edges in $L(K_{n})$, it suffices to note that $\forall v \in V(L(K_{n}))$, $deg(v)=2(n-2)$, and to use the fact that $\sum\limits_{v \in V(L(K_{n}))}deg(v)=2|E(L(K_{n}))|$.