Nearly Complete Graph

A graph is a collection of vertices and edges. A graph is complete if there is an edge connecting every vertex to every other vertex. A graph is nearly complete if it can be obtained by removing a small number of edges from a complete graph relative to the size of the graph.

Mathematical Definition

Consider a graph with vertices $v$, edges $e$, and genus $g$.

Calculate

$X=(e-3v+6)/6$.

Let $\lceil X\rceil$ denote the smallest integer greater than or equal to $X$. All graphs satisfy Euler's lower bound

$g\geq \lceil X\rceil$ .

For complete graphs $g=\lceil X\rceil$ and the bound is saturated.

One may start with a complete graph and remove $p$ edges such that the remaining graph satisfies

• Euler's lower bound is saturated $g=\lceil X\rceil$
• The graph is connected

Let $NC(n)$ denote the maximum number of possible edge removals from the complete graph $K_{n}$ such that the above two properties hold no matter which edges are removed. A graph with $n$ vertices is nearly complete if it can be obtained by removing $p\leq NC(n)$ edges from the complete graph $K_{n}$.

References

• The genus of nearly complete graphs-case 6, Jonathan L. Gross, Aeq. Math. 13, 243–249 (1975) doi:10.1007/BF01836527