Show that for any edge $e\in E(G)$, $κ(G−e)\geκ(G)−1$. ($e$ is an element of the edge set, $κ(G)$ is vertex connectivity)
I think this follows from Mengers theorem, but I am having trouble seeing how.
Show that for any edge $e\in E(G)$, $κ(G−e)\geκ(G)−1$. ($e$ is an element of the edge set, $κ(G)$ is vertex connectivity)
I think this follows from Mengers theorem, but I am having trouble seeing how.
If you can make $G-e$ disconnected by removing $k=\kappa(G-e)$ vertices, then removing the same $k$ vertices from $G$ either makes $G$ disconnected as well or turns $e$ into a bridge and then removing one of the end points of $e$ disconnects $G$; hence $\kappa(G)\le k+1$.