# Vertex connectivity question

I'm currently learning about vertex connectivity and I'm having a bit of trouble understanding some of the terms/definitions, namely "local connectivity" and "$k$-connected" and "connectivity of $G$" (definition $2$, $3$ and $4$) -

I tried finding the vertex connectivity of the following graph $G$:

I know that you can also find the vertex connectivity by finding the minimum cardinality of a vertex cut of $G$ which is clearly one, but I want to know how to get this answer by looking at internally disjoint paths.

If the minimum cardinality of a vertex cut of $G$ is one then does that mean there should be one pairwise internally disjoint $(x,y)$-path in $G$ (where $x,y$ are distinct vertices from the graph $G$)?

Yes, if $G$ is not complete then the minimum cardinality of a vertex cut is $k$ if and only if there is some pair of vertices $x,y$ such that $p(x,y)=k$. This is Menger's theorem. (We usually count a set of $n-1$ vertices as a vertex cut for this purpose, so that Menger's theorem also works in the complete graph case; the connectivity of $K_n$ is $n-1$ and any two vertices have exactly $n-1$ vertex-disjoint paths.)
In your case any choice of $x$ from the left-hand side of your graph and $y$ on the right-hand side will work. For example, $p(a,d)=1$ because every path from $a$ to $d$ must pass through $c$, so you can't have two vertex-disjoint paths.
• Hi @Especially Lime, thank you for taking the time to help me out! I think I'm beginning to understand it more. I just have one question regarding the "pairwise" part in the definition of local connectivity (definition 2). Taking vertices $a$ and $d$ for example, if $p(a,d)=1$ as you have deduced doesn't that mean there is one pairwise internally disjoint $(a,d)$-path? I'm a bit confused about the "pairwise" bit because it sounds like you need two (or a pair of) paths or something. – user450248 Jun 21 '17 at 11:56
Let's compute $p(u, v)$ for all pairs of distinct vertices $u$ and $v$: $$\begin{array}{|c|c|c|c|c|c|c|} \hline v\backslash u & a & b & c & d & e & f\\\hline a & - & 2 & 2 & 1 & 1 & 1 \\\hline b & 2 & - & 2 & 1 & 1 & 1 \\\hline c & 2 & 2 & - & 1 & 1 & 1 \\\hline d & 1 & 1 & 1 & - & 2 & 2 \\\hline e & 1 & 1 & 1 & 2 & - & 2 \\\hline f & 1 & 1 & 1 & 2 & 2 & - \\\hline \end{array}$$ So it is easy to see that $\kappa(G) = \min\{\,p(u, v) \colon u, v \in V(G), u \ne v\,\} = 1$.