0
$\begingroup$

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?

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

You might want to read this: Menger's Theorem

$\endgroup$

You must log in to answer this question.