# When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$

Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges." and "The maximum number of edges for an undirected graph is $$|V|(|V|-1)/2$$". Then why do even use $$|E| = \Theta (|V|^2)$$?, understand that $$\Theta$$ is the correct(tightest) bound in asymptomatic notation. It seems to me that $$|E| = \Theta (|V|^2)$$ can never happen, so why do we use it?

Note that asymptotic bounds only apply to infinite sequences.

In this case, $$|E| = \Theta(|V|^2)$$ applies to an implicit infinite sequence of graphs $$G_i=(V_i,E_i)$$, meaning that there are two positive constants $$c,c'$$ such that, $$c\cdot|V_i|^2 \leq |E_i| \leq c'\cdot|V_i|^2$$ whenever $$i$$ is large enough.

This constraint can be satisfied. For every $$i\in \mathbb N$$, take $$G_i$$ to be the complete graph on $$\{1,\ldots, i\}$$. Hence, $$G_i$$ has exactly $$i\cdot(i-1)/2$$ edges. For large enough $$i$$, we have $$\frac{1}{4}i^2 \leq \frac{i\cdot(i-1)}{2} \leq \frac{1}{2}i^2$$ So, we can say that $$|E| = \Theta(|V|^2)$$.

Another sequence could be constructed taking "almost complete" graphs, where we remove one edge from each complete graph $$G_i$$ in the previous sequence. This would still satisfy the bound.

We could even remove, say, $$100*i$$ edges from each $$G_i$$ (when possible) and still satisfy the bound. This is because we only care about $$|E_i|$$ growing with "quadratic speed".

• Balanced complete bipartite graphs $K_{\lceil n/2\rceil,\lfloor n/2\rfloor}$ (with about $n^2/4$ edges) are a good example to show that there are dense graphs that aren't just "cliques with a few edges removed". – David Richerby Jan 14 '19 at 16:50

You're absolutely right that $$\Theta$$ is the tightest asymptotic bound. But it's still asymptotic, and that means that we don't care about constant factors or terms of lower degree: when $$n$$ (or $$v$$ or whatever) gets big enough, the smaller terms become negligible.

In this case, $$\frac{v(v-1)}{2} = \frac{1}{2} v^2 + \frac{-1}{2} v$$. So removing the constant factors and lower terms leaves us with $$v^2$$.

• I don't understand your last paragraph. It doesn't make sense to use $\Theta$ on a single graph anyway, since there's nothing to go to infinity. But $\Theta$ absolutely includes a lower bound. – David Richerby Jan 14 '19 at 15:16
• @DavidRicherby Sorry, let me rephrase: using $\Theta$ implies that you can put a lower bound on how many edges are in a graph, in terms of the number of vertices. But the lower bound is always zero. So I would use $O$, which is only concerned with the upper bound (and it is in fact bounded above in terms of the number of vertices). – Draconis Jan 14 '19 at 16:43
• But asymptotic bounds don't apply to single graphs. We need to be talking about classes of graphs being dense and, in that case, we absolutely need to use $\Theta$ because it's precisely the lower-bound that defines density. If we just said "A class of graphs is dense if the $n$-vertex members of the class have $O(n^2)$ edges", then every class would be dense. – David Richerby Jan 14 '19 at 16:49
• @DavidRicherby Ahh, I see what you mean, I misread the question. I thought they were saying the number of edges in a general simple undirected graph was $\Theta(n^2)$ (not specifically in a dense graph), which makes no sense because there isn't a lower bound there. – Draconis Jan 14 '19 at 16:53