Give a proof or a counterexample: Every $k$-connected graph is $k$-edge connected.
Definition: A graph is $k$-connected if its connectivity is at least $k$. The connectivity of $G$ is the minimum size of a vertex $S$ such that $G-S$ is disconnected or has only one vertex.
Definition: A graph $G$ is $k$-edge connected if every disconnecting set has at least $k$ edges.
I thought this was false, but apparently it is true.
The graph I came up with was:
For instance, it is 2-connected, since we need at least $2$ vertices to disconnect it (those vertices in purple on the left). But it is 3-edge connected.
What am I misunderstanding here?
Best Answer
Your example is not a counterexample. It is $2$-edge connected because every disconnecting set has at least $2$ edges. Just because there exists a stricter lower bound of $3$ doesn't mean it isn't $2$-edge connected.