minimally k edge connected graph

Question

Suppose $G = (V,E)$ is minimally k edge connected, meaning $\forall e \in E$, $G - e$ is less than k edge connected. I want to show the minimum degree of the graph is k. I was thinking suppose the min. degree $> k$ at say vertex $v$, then this contradicts $G$ being minimally k edge connected, but I am not sure how to proceed.

Answer 1

If $G$ is minimally $k$-edge-connected, then every edge of $G$ is part of some cut of size $k$. (Given any edge $e$, there must be a size-$(k-1)$ cut in $G-e$, by minimality. Together with $e$ itself, this gives a size-$k$ cut in $G$ containing $e$.)

For $S \subseteq V(G)$, let $[S,\overline{S}]$ denote denote the number of edges from $S$ to $\overline{S} = V(G) \setminus S$.

Choose $X \subseteq V(G)$ to be a smallest set of vertices with $|[X, \overline{X}]|= k$. We'd like to show that $X$ consists of just a single vertex, because then we've found a vertex of degree $k$.

Suppose for the sake of contradiction that $X$ is larger than that. Let $e$ be any edge inside $X$, and let $Y$ be a set of vertices with $|[Y, \overline{Y}]| = k$ and $e \in [Y, \overline{Y}]$. In general, for any $X, Y \subseteq V(G)$, we have $$ |[X \cap Y, \overline{X \cap Y}]| + |[X \cup Y, \overline{X \cup Y}]| \le |[X, \overline{X}]| + |[Y, \overline{Y}]| $$ because:

• both sides count edges from $X \cap Y$ to $X \cap \overline{Y}$ once;
• both sides count edges from $X \cap Y$ to $\overline{X} \cap Y$ once;
• both sides count edges from $\overline{X} \cap Y$ to $\overline{X} \cap \overline{Y}$ once;
• both sides count edges from $X \cap \overline{Y}$ to $\overline{X} \cap \overline{Y}$ once;
• both sides count edges from $X \cap Y$ to $\overline{X} \cap \overline{Y}$ twice;
• only the right-hand side counts edges from $X \cap \overline{Y}$ to $\overline{X} \cap Y$.

In this particular case, we have $|[X, \overline{X}]| = |[Y, \overline{Y}]| = k$, and by $k$-connectedness, $[X \cap Y, \overline{X \cap Y}]$ and $[X \cup Y, \overline{X \cup Y}]$ can't be smaller than $k$, so they also both have size $k$.

But now $X \cap Y$ is a strictly smaller set than $X$ with $|[X \cap Y, \overline{X \cap Y}]| = k$, contradicting the way we chose the set $X$. So it's impossible for $X$ to contain more than a single vertex, and therefore we've found a vertex of degree $k$.