# 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 ${\displaystyle v}$, edges ${\displaystyle e}$, and genus ${\displaystyle g}$.

Calculate

${\displaystyle X=(e-3v+6)/6}$.

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

${\displaystyle g\geq \lceil X\rceil }$ .

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

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

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

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