Let $G$ a $k-$connected graph, then $L(G)$ is $(k-2)-$connected.

Question

Let $G$ a $k-$connected graph, then $L(G)$ is $(k-2)-$connected. Where $L(G)$ is the line graph of $G$.

I am very stuck in this problem. Try using Whitney's theorem for k-connected graphs.

Answer 1

For any graph $H$ let $L(H)$ denote the line graph of $H$, and for each edge $e \in E(H)$ write the vertex in $L(H)$ that corresponds to $e$ as $u(e)$. First note the following:

• (a) $L(H)$ is connected iff $H$ is connected
• (b) $L(H \setminus \{e\}) = L(H) \setminus \{u(e)\}$, and $L(H \setminus S) = L(H) \setminus \{u(e); e \in S\}$ for any subset $S$ of $E(H)$.
• (c) A $k$-connected graph $G$ is $k$-edge-connected.

So let $U$ be a set of $k-1$ vertices in $L(G)$. Then from (b) $L(G) \setminus U$ $=$ $L(G \setminus S)$ where $S =\{e; u(e) \in U\}$, and where $|S|=|U|$. Now, if $G$ is $k$-connected then (c) implies that $G$ is $k$-edge-connected which implies that $G \setminus S$ is connected. This in turn implies from (a) that $L(G \setminus S)$ is connected. And so as $L(G \setminus S)=L(G) \setminus U$, that $L(G \setminus U)$ is also connected.

So by definition $L(G)$ is $k$-connected, which implies that $L(G)$ is $(k-2)$-connected.