# 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}$ .