Is node connectivity simply the smallest node degree in the network?

Question

I was reading Network Science with Python and NetworkX, which has the following definition:

The node connectivity is the smallest min-cut over all node pairs. The edge connectivity is defined similarly.

It then proceeds to show that Zachary's Karate Club, as well as several other examples, has a node connectivity of 1. Does this simply means that there exists a node with a single edge (i.e. a degree of 1)?

In general, could the node connectivity ever exceed the smallest degree node in the network? Will it ever be less than that?

Answer 1

Definitions are adopted from "Graph Theory" by Reinhard Diestel. All considered graphs are finite, simple and undirected.

A graph $G=(V,E)$ is $k$-connected (for $k \in \mathbb{N}$) if $|G| > k$ and $G-X$ is connected for every set $X \subseteq V$ with $|X| < k$. In other words, no two vertices of $G$ are separated by fewer than $k$ other vertices. We call the greatest integer $k$ such that $G$ is $k$-connected the connectivity of $G$ and denote it by $\kappa(G)$.

If $|G| > 1$ and $G-F$ is connected for every set $F \subseteq E$ of fewer than $l$ edges, then $G$ is $l$-edge-connected. The greatest integer $l$ such that $G$ is $l$-edge-connected is the edge-connetivity $\lambda(G)$ of $G$.

The following inequalities are due to Whitney.

Theorem: Let $G=(V,E)$ be a graph with minimum degree $\delta(G)$, then $\kappa(G) \leq \lambda(G) \leq \delta(G)$.

Proof Sketch: Consider a vertex $v$ of minimum degree $deg(v)=\delta(G)$. By removing $deg(v)$ edges that are incident to $v$, $G$ becomes disconnected. We need to show that $\kappa(G) \leq \lambda(G)$. Let $X \subset E$ be the set of edges incident to $v$. Find a set of at most $|X|$ vertices that disconnects $G$ (this is relatively straight forward by the way). Deleting a vertex, also deletes every edge that is incident to that vertex (using this, we can show that assuming $\lambda(G) < \kappa(G)$ leads to contradiction).

Answer 2

I'm going to have a stab at a proof too, please feel free to leave any feedback on this.

Suppose that you had a graph $G = (V, E)$ that is $\kappa$-connected. Let $\delta(G)$ be the minimum degree.

Suppose that $\kappa(G) > \delta(G)$. Now select $v \in V$ that has degree $\delta(G)$. Now remove $\delta(G)$ edges from $v$. By selection, this vertex must now be disconnected, which would mean that $G$ had been disconnected by removing fewer than $k$ edges, which contradicts the claim that $\kappa(G) > \delta(G)$.

To prove that $\kappa(G) \le \delta(G)$, consider the following examples.

First, consider a graph with two nodes with a single undirected edge connecting them. In this case, both nodes have a degree of 1, and the graph would become disconnected by removing the single edge. In this case, clearly $\kappa(G) = \delta(G) = 1$.

Secondly, consider the following graph:

In this case, $\delta(G) = 2$ and $\kappa(G) = 1$, so $\kappa(G) < \delta(G)$. Therefore, it is possible that either $\kappa(G) = \delta(G)$ or $\kappa(G) < \delta(G)$, but it is not possible that $\kappa(G) > \delta(G)$. Therefore, $\kappa(G) \le \delta(G)$.