Doubt in vertex connectivity less than edge connectivity proof

Question

Sir i recently started graph theory. Pls clarify my doubt. I understood the reason why edge connectivity is less than min degree(remove all vertices incident to min degree vertex). I have doubt in 2nd part of proof when given graph is not complete graph. Here Pls see case 2 in this link. https://www.imsc.res.in/~vikram/DiscreteMaths/2011/connectivity.pdf (in page num 2)

If graph is not complete then there exists x, y are vertices in S,S' respectively, so that xy is not edge. If that is the case why x and y are in edge set. In proof he says there is indirect path between x,y (x to x neighbour in S and then to y or x or y neighbour in S' and then to y). In this case, my edge set should consist of x neighbour(instead of x) in S to y or x to y-neighbour in S' instead of y. So x,y will not be part of S, S'. Edge set [S,S'] i am assuming as edges between S to S'. Actually i am confused here. Pls clarify my doubt

Answer 1

$\qquad$Let $G = (V,E)$ be a connected noncomplete graph. A vertex connectivity of graph $G$, denoted by $\kappa(G)$, is a minimum number of vertices in a vertex cut. An edge connectivity of graph $G$, denoted by $\lambda(G)$, is a minimum number of edges in an edge cut. We need to show for graph $G$ $$\kappa(G) \leq\lambda(G) $$ is true.
$\qquad$ We assume the opposite, $\kappa(G) >\lambda(G) $ , is true. Assume that we want to remove a single vertex to disconnect our graph $G$. Based our assumption we must remove $0$ edge. If such a vertex exists, then our original graph $G$ is not a connected graph. That is, the final statement leads to the contradiction, because we defined $G$ to be a connected graph.

Answer 2

I found one valuable proof in one online book.

proof_1:

Removing a vertex also removes all of the edges incident with it, which suggests that $\kappa(G)\le \lambda(G)$.

To say this more specifically, assume $\kappa(G)> \lambda(G)$.

Based on $\lambda(G)$, we take one group of edges (let it be $E_1(G)$) sharing one endpoint $v_1$ , we choose $v_1$, then do this again and again until all the remaining edges share no endpoint with each other. Assume here we have chosen $v_{1\sim k}$ and $E_{1\sim k}(G)$, obviously $|v_{1\sim k}|=k\le |\bigcup_{i=1}^k E_{i}(G)|$. (Here I use $v_{1\sim k}$ to denote the sequence $v_1,v_2,\ldots,v_k$, similarly for other notations with $\sim$) Then for the rest edges, we choose one endpoint of each edge. Assume we choose endpoints $v_{(k+1)\sim m}$ from $E(G)\setminus \bigcup_{i=1}^k E_{i}(G)$.

Then we find one edge cut $v_{1\sim m}$ which is less than $\lambda(G)$, leading to the contradiction. So $\kappa(G)\le \lambda(G)$.

---

proof_2:

Here I give some notes for it instead of rephrasing it because the book doesn't say much difficult to understand:

1. If v and w are the only vertices of G , G is $K_2$ and has connectivity 1 .

   corresponds to

   If there is no cutset and G has at least two vertices, we say G has connectivity n−1 ;

   which will cause the graph only having one vertex.

2. As a special case we note that if $\lambda=n−1$ then $\delta=n−1$,

   This is shown by $\lambda(G)\le \delta(G)$

3. so G is $K_n$ and $\kappa =n−1$.

   is due to

   there are graphs without a cutset: the complete graphs $K_n$.

4. Since k<n−1 , $k−1\le n−3$ , and so $G_2$ has at least 3 vertices.

   is due to there are totally $n$ vertices.

5. The last paragraph is based on splitting all possible conditions into cases

   1. $v,w\in V(G_2)$

      then either $e_k$ "produces a connected graph" or not

   2. $\neg (v,w\in V(G_2))=(v\not\in V(G_2))\vee (w\not\in V(G_2))$

---

proof_3

I found one proof when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen. This problem is same as exercise 10.4-55. I encountered with this problem before doing this exercise. The solution of the book is as the following:

Let G be a graph with n vertices; then $\kappa(G) \le n−1$. Let C be a smallest edge cut, leaving a nonempty proper subset S of the vertices of G disconnected from the complementary set $S' = V - S$. If xy is an edge of G for every $x \in S$ and $y \in S'$ , then the size of C is $|S||S'|$, which is at least n - 1, so $\kappa(G) \le \lambda(G)$. Otherwise, let $x \in S$ and $y \in S'$ be nonadjacent vertices. Let $T$ consist of all neighbors of $x$ in $S′$ together with all vertices of $S - {x}$ with neighbors in $S'$ . Then $T$ is a vertex cut, because it separates $x$ and $y$. Now look at the edges from x to $T \cap S'$ and one edge from each vertex of $T \cap S$ to $S'$ ; this gives us |T| distinct edges that lie in C, so $\lambda(G) = |C| \ge |T| \ge \kappa(G)$.

I add some notes for it based on the same reason as proof_2

1. Here $C$ must disconnect $G$ into 2 connected components because if more than 2, then some edges in $C$ can be not removed to construct only 2 connected components leading to the contradiction with "smallest".

2. The all possibilities are splitted into 2 cases, either $P=\exists x\in S,y\in S' (xy\in E(G))$ (Here $E(G)$ is the edge set of $G$) or $\neg P$.

3. because it separates $x$ and $y$

   This is due to: to go from $x$ to $y$ which are not adjacent, we either go through something which can reach $S'$ in $S$ or not.