Large graph connectivity implies both many and few edges?

27 Views Asked by At

Let $G$ be a simple graph with $v$ vertices, $e$ edges, and edge connectivity $c$. Since $2e / v$ is the average degree of all vertices, we must have $c \leq 2e / v$, since there is some vertex with degree $\leq 2e / v$.

This relation is simple. For a fixed number of vertices, you need more edges to be more connected. However, it implies another inequality that seems to say the exact opposite.

The inequality is equivalent to $v \leq 2e / c$. Given an upper bound for $v$, we immediately obtain an upper bound for $e$, namely $$e \leq \frac{1}{2} \frac{2e}{c} \left( \frac{2e}{c} - 1 \right).$$ Since $e$ is always bounded by $D = v(v - 1) / 2$, we also obtain $$e \leq \frac{1}{2} \frac{D}{c} \left( \frac{D}{c} - 1 \right).$$

Now this says that for a fixed number of vertices, you need fewer edges as connectivity grows! This seems to contradict my interpretation of the first inequality. Have I made a mistake somewhere, or am I interpreting something wrong?

1

There are 1 best solutions below

3
On BEST ANSWER

Your last inequality is trivial though, even for $c = n-1$ (and you are missing a couple of factors of 2 on the RHS). Your last inequality with the missing factors of 2 put into the RHS (and $c = n-1$) yields $e \le \frac{n(n-1)}{2}$.