3
$\begingroup$

The following is a theorem given in Bella Bollobas's Modern graph theory(Springer 2002) Page-73

If $G$ is nontrivial (that is, has at least two vertices), then the parameters $\delta(G)$, $\lambda(G)$ and $\kappa(G)$ satisfy the following inequality: $\kappa(G) \le \lambda(G) \le \delta(G)$, where $\delta(G)$ is the minimum degree of a vertex, $\lambda(G)$ is the edge connectivity, and $\kappa(G)$ is the vertex connectivity.

Proof:

Indeed, if we delete all the edges incident with a vertex, the graph becomes disconnected, so the second inequality holds. To see the other inequality, note first that if $G$ is complete then $\kappa(G) = \lambda(G) = |G| - 1$, and if $\lambda(G) \le 1$ then $\lambda(G) = \kappa(G)$. Suppose now that $G$ is not complete, $\lambda(G) = k \ge 2$, and $\{x_1 y_1, x_2 y_2, \ldots , x_k y_k\}$ is a set of edges disconnecting $G$. If $G - \{x_1, x_2, \ldots , x_k\}$ is disconnected then $\kappa(G) \le k$. Otherwise, each vertex $x_i$ has degree at most $k$ (and so exactly $k$). Deleting the neighbours of $x_1$, we disconnect $G$. Hence $\kappa(G)\le \lambda(G)$.

I did not understand the following part of the proof: "Otherwise, each vertex $x_i$ has degree at most $k$ (and so exactly $k$)" . Why is this true? I would really appreciate an elaborate answer to this.

$\endgroup$
2
$\begingroup$

I don’t see how to justify the statement in question, but I do see how to justify a weaker statement that is still sufficient to prove the theorem.

Suppose that $G-\{x_1,x_2,\ldots,x_k\}$ is connected and and $\deg v_i>k$ for each $i\in\{1,\ldots,k\}$. Then each $v_i$ has at least $k+1$ neighbors in $G$, and at most $k-1$ of them can be in $\{x_1,x_2,\ldots,x_k\}$, so there must be at least two vertices $u_i$ and $v_i$ in $G-\{x_1,x_2,\ldots,x_k\}$ that are neighbors of $x_i$ in $G$. At least one of $u_i$ and $v_i$ must be different from $y_i$; say $u_i\ne y_i$. I claim that this implies that $G-\{x_1y_1,\ldots,x_ky_k\}$ is connected, which is a contradiction.

Let $v$ and $w$ be any two vertices of $G$. If $v,w\notin\{x_1,\ldots,x_k\}$, then there is a path from $v$ to $w$ in $G-\{x_1,\ldots,x_k\}$ and hence in $G-\{x_1y_1,\ldots,x_ky_k\}$. If $v=x_i$ and $w\notin\{x_1,\ldots,x_k\}$, there is a path $P$ from $w$ to $u_i$ in $G-\{x_1y_1,\ldots,x_ky_k\}$, and we can add the edge $u_ix_i$ to $P$ to get a path from $w$ to $x_i$ in $G-\{x_1y_1,\ldots,x_ky_k\}$. Finally, if $v=x_i$ and $w=x_j$ with $i\ne j$, there is a path $P$ from $u_i$ to $u_j$ in $G-\{x_1y_1,\ldots,x_ky_k\}$, and we can extend it with the edges $x_iu_i$ and $u_jx_j$ to get a path from $x_i$ to $x_j$ in $G-\{x_1y_1,\ldots,x_ky_k\}$. This proves the claim.

This contradiction shows that there must be at least one $i\in\{1,\ldots,k\}$ such that $\deg x_i\le k$, and since we already know that $k=\lambda(G)\le\delta(G)\le\deg x_i$, we must have $\deg x_i=k$. Deleting the neighbors of $x_i$ disconnects $G$, so $\kappa(G)\le k=\lambda(G)$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.