Skip to main content
Post Made Community Wiki
Source Link
Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279

Theorem 5.10 of http://www-math.mit.edu/~rstan/algcomb.pdf is proved by elementary group theory and linear algebra. It states the following:

(a) Fix $m\geq 1$. Let $p_i$ be the number of
nonisomorphic simple graphs with $m$ vertices and $i$ edges. Then the
sequence $p_0, p_1,\dots,p_{{m\choose 2}}$ is symmetric and unimodal. (This means that $p_i=p_{{m\choose 2}-i}$ and $p_0\leq p_1 \leq \cdots \leq p_{\lfloor \frac 12{m\choose 2}\rfloor}$. The symmetry propery is trivial, but unimodality is another story.)

(b) Let $T$ be a collection of nonisomorphic simple graphs with $m$ vertices such that no element of $T$ is isomorphic to a spanning subgraph of another element of $T$. Then $|T|$ is maximized by taking $T$ to consist of all nonisomorphic simple graphs with $\lfloor \frac{1}{2}{m\choose 2}\rfloor$ edges.

Many similar results can be proved using the techniques of the above link.