Prove that if $G$ is $k$-edge connected, then $G \bigvee K_1$ is $k+1$-edge connected.
Since $G$ is $k$-edge connected, $G$ has at least $k$ bridges. Let $H=G \bigvee K_1$, $X \subset E(H)$ , and let $v \in V(K_1)$.
I'm trying to prove this by contradiction, so assume that $|X| \leq k$. I know that each bridge is incident to at least 1 cut-vertex. Is it legal for me to say that because $|X| \leq k$, the set of minimum vertex cut $S$ has at most $k$ vertices?
Best Answer
The proof is almost the same with Prove that if $G$ is a $k-connected$ graph, then $G \bigvee K_1$ is $k+1$ connected graph
Let $H = G \bigvee K_1$ and $v$ is the only node in $K_1$. First, $|G| \ge k+1$, since it is $k+1$ edge connected. Now, consider any cut $S$ of $H$, and let's say it divides the nodes of $H$ into two disjoint sets $A$ and $B$. If either $A = \{v\}$ or $B = \{v\}$, then clearly the minimum cut is $k+1$ ($S$ is equal to all the edges from $v$). Otherwise, let us assume that $v \in A$. Then, $A - \{v\}$ and $B$ form a non-empty cut over the original graph $G$ -- thus, it must consist of at least $k$ edges not adjacent to $v$. In addition, $S$ must consist of all the edges connecting $v$ to any node in $B$, and since $B$ is not empty, it means that $S$ must also contain at least one edge adjacent to $v$. Thus, $S$ must consist of at least $k+1$ edges.