Prove Your Intuitions About Graph Connectivity

Prerequisites

  • Vertex cut
  • $k$-connected
  • Minimum degree $\delta(G)$ of a graph
  • Connectivity $K(G)$ of a graph

Intuitions

A decently connected graph should not contain any weak vertex.

If there does not exist any weak vertex, can we conclude that, at least in some condition, a graph should be highly connected?

Proofs

What do we mean by weak vertices? Well, it is a vertex with low degrees. If there exits a vertex with low degree, then the graph should not be more connectivity than that degree.

Lemma

Let $G$ be a connected graph. Then,
$$
K(G) \le \delta (G)
$$

Proof

Let $x$ be a vertex of the minimum degree, i.e. $d(x)=\delta(G)$.

Say $x$ is the weak vertex.

Then, let $W=N(x)$.

$W$ is the set containing all the neighbours of $x$ in $G$.

What would happen if we remove $W$ from $G$? Is $G$ still connected?

Let $S=G\setminus ( \{x\}\cup W) $.

$S$ denotes the remainder of $G$ after we remove the weak vertex and its neighbourhood. Why consider this?

Assume that $S=\emptyset$. Note that
$$
|V(G)| = |(\{x\}\cup W)| = |W| + 1
$$
By definition, $G$ must have at least $K(G)+1$ vertices.

Note that $G$ is $K(G)$-connected. Then, by definition of connectivity, $G$ has at least $K(G)+1$ vertices.

$$
|V(G)| \ge K(G)+1 \implies |W| \ge K(G) \implies \delta(G) \ge K(G)
$$

Assume that $S\ne \emptyset$. Note that $W$ is a vertex cut of size $\delta(G)$. $G\setminus W$ has two components $\{x\}$ and $S$.

Hence, $W$ is not $\delta(G)$ connected. $K(G) \le \delta(G)$. This completes the proof.


Now then, we have proved our first intuition. Our second intuition is

If there does not exist any weak vertex, can we conclude that, at least in some conditon, a graph should be highly connected?

Our intuition is not exactly true; if we have two complete graphs as components, the graph has connectivity $0$ but the minimum degree of the graph may be huge.

However, if the minimum degree is large enough, this implies the graph has a large number of edges. If it contains too many edges, then the graph is kept connected; based on a connected graph, we can conclude that the graph is highly connected.

Lemma

Let $G$ be a graph with $n$ vertices and let $1 \le k \le n-1$. Then, if $\delta(G)\ge \frac{n+k-2}{2}$, then $G$ is $k$-connected.

Proof

Let $G$ be a graph such that $|V(G)|=n$ and $\delta(G) \ge \frac{n+k-2}{2}$. Assume for contradiction that $G$ is not $k$-connected. That is, $G$ has a vertex cut $W$ such that $|W|<k$.

Let $H$ denote the smallest component in $G-W$. $H$ has at most $\frac{n-|W|}{2}$ vertices.

If $H$ has more vertices than that, $H$ would not be the smallest component. Otherwise, the sum of vertices in two components already exceeds the number of total vertices, a contradiction.

Let $x$ be a vertex in $W$. Note that $x$ may only connect to vertices in $(H\setminus \{x\})\cup W$.
$$
d(x) \le |H|-1+|W| \le \frac{n-|W|}{2}-1+|W|=\frac{n+|W|-2}{2}
$$
Since $|W|<k$ by assumption, we have
$$
d(x) \le \frac{n+|W|-2}{2} < \frac{n+k-2}{2}
$$
This is a contradiction. Hence, $G$ is $k$-connected.

The contradiction came from the fact that the vertex in $H$ has to connect more vertices outside of $W$ and $H$. This means any vertex cut should be larger than $W$.