1
$\begingroup$

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$)?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user450248 Jun 21 '17 at 11:56
  • $\begingroup$ No problem :) What it really means for a collection of paths to be "pairwise internally disjoint" is that there aren't any bad pairs of paths, where a bad pair is two paths with an internal vertex in common. When there's only one path, there aren't any pairs at all, so there can't be any bad pairs, so it must be pairwise internally disjoint. It's a bit of an unfortunate phrasing when there's only one path though. $\endgroup$ – Especially Lime Jun 21 '17 at 12:19
  • $\begingroup$ Ahhh that makes a lot more sense now. Thank you so much! $\endgroup$ – user450248 Jun 21 '17 at 12:21
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy