Showing edge-connectivity greater than vertex-connectivity

243 Views Asked by At

The following is quoted from Diestel's Graph Theory:

Proposition 1.4.2. If $G$ is non-trivial then $\kappa(G) \leqslant \lambda(G) \leqslant \delta(G)$.

Proof. The second inequality follows from the fact that all the edges incident with a fixed vertex separate $G$. To prove the first, let $F$ be any minimal subset of $E$ such that $G-F$ is disconnected. We show that $\kappa(G) \leqslant|F|$

Suppose first that $G$ has a vertex $v$ that is not incident with an edge in $F$. Let $C$ be the component of $G-F$ containing $v$. Then the vertices of $C$ that are incident with an edge in $F$ separate $v$ from $G-C$. Since no edge in $F$ has both ends in $C$ (by the minimality of $F$ ), there are at most $|F|$ such vertices, giving $\kappa(G) \leqslant|F|$ as desired.

Suppose now that every vertex is incident with an edge in $F$. Let $v$ be any vertex, and let $C$ be the component of $G-F$ containing $v$. Then the neighbours $w$ of $v$ with $v w \notin F$ lie in $C$ and are incident with distinct edges in $F$, giving $d_{G}(v) \leqslant|F|$. As $N_{G}(v)$ separates $v$ from all the other vertices in $G$, this yields $\kappa(G) \leqslant|F|$-unless there are no other vertices, i.e. unless $\{v\} \cup N(v)=V$. But $v$ was an arbitrary vertex. So we may assume that $G$ is complete, giving $\kappa(G)=\lambda(G)=|G|-1$.

$F$ is a minimal subset of edges such that $G\setminus F$ is disconnected. This means take the minimal subset out of the collection of subsets which make $G$ disconnected after their removal. If $\kappa(G)\leq |F|$, why does this imply that $\kappa(G)\leq \lambda(G)$? Moreover, does $\lambda(G)=F$?