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:

enter image description here

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?


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.


Your Answer

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