κ(G) ≤ λ(G) ≤ δ(G) ≤ 2|E(G)|/|V(G)| ≤ Δ(G)

Relation of Min Vertex Cutsets, Min Edge Cutsets, The Minimum Degree, and Maximum Degree

We are going to prove the following inequality relating the minimum vertex cutset $\kappa (G)$, the minimum edge cutset $\lambda (G)$, the minimum degree in a graph $\delta (G)$, and the maximum degree in a graph $\Delta (G)$.

(1)

\begin{align} \kappa (G) ≤ \lambda (G) ≤ \delta (G) ≤ 2 \frac{| \: E(G) \: |}{| \: V(G) \: |} ≤ \Delta (G) \end{align}

We will not prove all of these components, however, we will prove a few of them.

Lemma 1: The minimum edge cutset of a graph $\lambda (G)$ is less than or equal to the minimum degree in a graph, $\delta (G)$, that is $\lambda (G) ≤ \delta (G)$.

• Proof: Suppose we have a graph G with a vertex $x \in V(G)$ where $\deg (x) = \sigma (G)$. If we take all of the edges incident with x and remove them, we obtain an edge cutset as vertex x will be isolated. We can always obtain an edge cutset this way. Hence, our minimum edge cutset will either be equal to our minimum degree or less. So $\lambda (G) ≤ \delta (G)$.

Lemma 2: The minimum degree in a graph, $\delta (G)$ is less than or equal to twice the number of edges of $G$ divided by the number of vertices in $G$, that is $\delta (G) ≤ \frac{2 \mid E(G) \mid }{\mid V(G) \mid}$.

• Proof: We acknowledge that $2 \frac{| \: E(G) \: |}{| \: V(G) \: |}$ represents the average degree in a graph G. Nevertheless we can prove this inequality algebraically. First we know by the Handshaking Lemma that:

(2)

\begin{align} \sum_{x \in V(G)} \deg (x) = 2 | \: E(G) \: | \end{align}

• Hence it follows that $\delta (G)$ is the minimum degree in the graph, then:

(3)

\begin{align} \sum \delta (G) ≤ \sum_{x \in V(G)} \\ n \delta (G) ≤ 2 | \: E(G) \: | \\ \delta (G) ≤ 2 \frac{| \: E(G) \: |}{n} \end{align}

• But we know that n represents the number of vertices in the graph. Hence:

(4)

\begin{align} \delta (G) ≤ 2 \frac{| \: E(G) \: |}{| \: V(G) \: |} \end{align}

Lemma 3: Twice the number of edges divided by the number of vertices $\frac{2 \mid E(G) \mid}{\mid V(G) \mid}$ is less than or equal to the maximum degree of $G$, $\Delta (G)$, that is $\frac{2 \mid E(G) \mid}{\mid V(G) \mid} ≤ \Delta (G)$.

• Proof: We will complete this proof in the same manner as the last lemma. By the Handshaking lemma we know that:

(5)

\begin{align} \sum_{x \in V(G)} \deg (x) = 2 | \: E(G) \: | \end{align}

• And we also know that if $\Delta (G)$ is the maximum degree in our graph, then:

(6)

\begin{align} \sum_{x \in V(G)} \deg (x) ≤ \sum \Delta (G) \\ \sum_{x \in V(G)} \deg (x) ≤ n \Delta (G) \\ 2 | \: E(G) \: | ≤ n \Delta (G) \\ 2 \frac{| \: E(G) \: |}{n} ≤ \Delta (G) \end{align}

• But n represents the number of vertices in G, hence we are done the proof and:

(7)

\begin{align} 2 \frac{| \: E(G) \: |}{| \: V(G) \: |} ≤ \Delta (G) \end{align}