Question regarding connectivity number and maximum degree of a graph

Question

I need to show for graph G,if $\Delta(G) \leq 3 $ then $\kappa(G) =\kappa^{'}(G)$.

Where $\Delta(G) \ $ is the maximum degree of the graph , $ \kappa(G) $ is the vertex connectivity number and $\kappa^{'}(G)$ is the edge connectivity number.

I tried to prove this using, whitney's theorem where it says , for any graph ,

$\kappa(G) \leq \kappa^{'}(G) \leq \delta(G)$ , where $\delta(G)$ is the minimum degree of G.

So $\kappa(G) \leq \kappa^{'}(G) \leq3 . $ But i dont have any clue to go further from this. Can anyone give me any clue to solve this ?

Thank you

Answer 1

I actually proved this as a homework a while ago. This could be proven if you know Menger's theorem. There are two versions:

Vertex-connectivity Menger's theorem (VMT): A graph G is k-connected if for all pairs of vertices x,y $\in$ V(G), there exists k pairwise internally disjoint (pid) x-y paths.

Edge-connectivity Menger's theorem (EMT): A graph G is k-edge-connected if for all pairs of vertices x,y $\in$ V(G), there exists k pairwise edge disjoint (ped) x-y paths.

Since $\Delta(G) \leq 3$, $\kappa'(G) \leq 3$. My approach is to show the statement for the cases $\kappa'(G) = 1,2,3$.

If $\kappa'(G) = 3$, then all vertices must have degree 3. A vertex cut would be the three neighbors of any vertex. This cut is minimal: by EMT, there are 3 ped's between any pair of vertices of G, and since $deg(v) = 3$ for all v, no vertices are on 2 ped's (which would make it having degree at least 4 => contradiction). So $\kappa(G)$ can't be less than 3. So $\kappa(G) = 3$

If $\kappa'(G) = 2$, then there must be a vertex of degree 2 and no vertices of degree 1. The neighbors of the vertex of degree 2 constitute a vertex cut. By the fact that the graph has no vertices of degree 1, this cut is minimal. So $\kappa(G) = 2$.

If $\kappa'(G) = 1$, then by EMT, there is a pair of vertices such that there is only one path connecting them. Any vertex on this path is a cut vertex. So $\kappa(G) = 1$.