$G$ is $n$-edge-connected iff $L(G)$ is $n$-connected

57 Views Asked by At

Please, give me feedback if the following argument about a graph $G$ and its line graph $L(G)$ is acceptable.

Let $G$ be a connected graph with minimum degree $\delta(G) \geq n > 1$. Then, $G$ is $n$-edge-connected if and only if $L(G)$ is $n$-connected.

Case 1 ($\supset$):

Let $wx,yz \in V(L(G)) = E(G)$ be distinct with $x \not= y$. Since $G$ is $n$-edge-connected, there are $n$ edge-disjoint paths $P_1,...,P_n \subseteqq G$ between $x$ and $y$, that is, $\forall \ell \in \{1,...,n\}: P_\ell = x v_\ell ...w_\ell y$ and $\forall \imath,\jmath \in \{1,...,n\}: (\imath\not=\jmath) \supset E(P_\imath) \cap E(P_\jmath) = \emptyset$.

Note that at most one $P_{\imath_0}$ contains $wx$ and $\forall \ell \in \{1,...,n\}: x v_\ell \cap xw \not= \emptyset$. Moreover, at most one $P_{\jmath_0}$ contains $yz$ and $\forall \ell \in \{1,...,n\}: w_\ell y\cap yz \not= \emptyset$.

We enlarge (where possible) the paths $P_\ell$ by the edges $wx$ and/or $yz$ to $P_\ell'$ such that $\forall \imath,\jmath \in \{1,...,n\}: (\imath\not=\jmath) \supset E(P_\imath') \cap E(P_\jmath') = \{wx,yz\}$.

When we consider the corresponding paths $Q_\ell$ in $L(G)$ which are derived from $P_\ell'$, then these $n$ paths are independent. Therefore, $L(G)$ is $n$-connected.

Case 2 ($\subset$):

Let $x,y \in V(G)$ be distinct. Choose different elements $w,z \notin V(G)$ and define $G' := (V(G) \cup \{w,z\}, E(G) \cup \{wx,yz\})$. Then, $d_{L(G')}(wx) \geq n$ and $d_{L(G')}(yz) \geq n$ by construction, and $L(G) \subseteqq L(G')$ where $L(G')$ is still $n$-connected. Hence, there are $n$ independent paths $P_1,...,P_n \subseteqq L(G')$ between $xw$ and $yz$, that is, $\forall \imath,\jmath \in \{1,...,n\}: (\imath\not=\jmath) \supset V(P_\imath) \cap V(P_\jmath) = \{xw,yz\}$.

Since $d_{G'}(w) = 1 = d_{G'}(z)$, it follows that these paths correspond to $n$ edge-disjoint paths in $G'$ between $x$ and $y$. These same paths exist also in $G$. Therefore, $G$ is $n$-edge-connected.