Determining the connectivity of this graph Determine the connectivity of the graph

I know that $\kappa(G)\leq4$ since $\delta(G)=4$, but beyond that I am not sure how to approach this. Any help is appreciated
 A: The naive approach: $\kappa(G)$ is the minimum of $\kappa(v,w)$ for all pairs of vertices $(v,w)$, where $\kappa(v,w)$ is the size of the minimum vertex cut between $v$ and $w$. We can compute $\kappa(v,w)$ by a network flow problem, but for a small graph with a nice visual representation, it might be easier to invoke Menger's theorem: $\kappa(v,w)$ is also the size of the largest collection of vertex-disjoint paths from $v$ to $w$ (that is, paths sharing no vertices other than $v$ and $w$). These paths can be found by hand.
This approach leaves you with $\binom{18}{2}$ computations of $\kappa(v,w)$, which seems painful (even if many of them are similar due to symmetry). A shorter approach (which I get from Algorithm 11 of this article) is the following:


*

*Pick any vertex $v$.

*Compute $\kappa(v,w)$ for all other vertices $w$ in the graph.

*Compute $\kappa(x,y)$ for all vertices $x,y$ which are neighbors of $v$.

*The minimum of all values computed in steps 2 and 3 is $\kappa(G)$. 


In our case, we suspect that $\kappa(G)=4$, and so by "Compute $\kappa(v,w)$" we really mean "Find four vertex-disjoint paths from $v$ to $w$, proving that $\kappa(v,w) \ge 4$". If we pick $v$ to be the bottom vertex of $G$ in the diagram (for example), then we can exploit $G$'s symmetry and "only" have to do $16$ of these calculations: $10$ in step 2 and $6$ more in step 3.
The reason that this works is that one of two possibilities must hold:


*

*Either there is a vertex cut of size $\kappa(G)$ separating $v$ from some other vertex $w$ of the graph, or

*The vertex $v$ itself is in every vertex cut of size $\kappa(G)$, in which case there is a vertex cut of size $\kappa(G)$ separating two of $v$'s neighbors from each other.


Steps 2 and 3 of the algorithm address these two possibilities, respectively.
