# 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 , edges , and genus .

Calculate

- .

Let denote the smallest integer greater than or equal to . All graphs satisfy Euler's lower bound

- .

For complete graphs and the bound is saturated.

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

- Euler's lower bound is saturated
- The graph is connected

Let denote the maximum number of possible edge removals from the complete graph such that the above two properties hold no matter which edges are removed. A graph with vertices is *nearly complete* if it can be obtained by removing edges from the complete graph .