Lower and Upper bound on number of edges in a simple and connected graph

Question

I was reading about Graph 3-coloring in Goldreich, Micali, Wigderson and they make a claim on pg. 712 that the edges and vertices of a simple and connected graph are polynomially related. Specifically, they say for a graph $G(V,E)$ with $|E|=m$ and $|V|=n$ that $n-1\leq m<\displaystyle\frac{n^2}{2}$. The lower bound seems correct according to other sources, but on other relevant stack exchange questions and wikipedia I find that the upper bound of such graphs is listed as $\displaystyle\frac{n(n-1)}{2}=\frac{n^2-n}{2}$.

So, did Goldreich et al. make a typo, or is there reasoning behind this claim?

Answer 1

What they've said is certainly still valid, since $\frac{n^2-n}{2} < \frac{n^2}{2}$ for $n \ge 1$.

It is not a tight bound, but it's commonly used for simplicity when the exact value doesn't matter. And the exact value doesn't matter here: all they need is that

1. There is an upper bound on $n$ which is polynomial in $m$.
2. There is an upper bound on $m$ which is polynomial in $n$.

(This is summarized in the paper as "$n$ and $m$ are polynomially related".)

This means that when we talk about a "polynomial-time algorithm", we don't have to distinguish between "polynomial in $n$" and polynomial in $m$": the two can be used interchangeably.