Show that if G is a graph, then $κ(G) ≤ λ(G)$ where $κ(G)$ is vertex connectivity and $λ(G)$ is edge connectivity
I have a solution that seems rather simple , could someone verify the correctness of my proof
Basic observation
- We must only consider the case when $G$ is connected and has three or more vertices.
- In a connected graph removing one vertex will remove at least one edge
- Also removing vertices of degree one , will only result in a connected sub graph
Solution:
Let $\lambda \left( G\right) =n$ and let $E=\left( e_{1},e_{2},\ldots ,e_{n}\right) $ be any set of $n$ edges that when removed will produce a disconnected graph .
Each edge will be incident on two vertices , let $v_{i_1}, v_{i_2}$ be the two vertices on which $e_{i}$ is incident . Then at least one of $v_{i_1}, v_{i_2}$ is a degree greater than 1. Since if we have each of degree one then we have a disconnected component of two vertices right here. Let $v_i$ be the vertex with greater degree among $v_{i_1}, v_{i_2}$, then $deg \left( V_{i}\right) \geq 2$
Then removing the vertices $\left( v_{1},v_{2},\ldots v_{2}\right) \\. $ will also remove $E$ thus producing a disconnected graph.
Thus we found a set vertex cut with $max(n)$ . Thus $κ(G) ≤ λ(G)$