A simple graph is one with no self-loops or multiple edges. Among the simple graphs with $n$ vertices and at most $20n − 3$ edges:
- There is always a graph with all vertices connected to at least $42$ other vertices.
- For all such graphs the number of vertices connected to at least $42$ other vertices is at most cn for some constant $c < 1$.
- There are no graphs with each vertex connected to at most $38$ other vertices.
- None of the above