# 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*.

Euler's lower bound is defined to be

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

If a graph is complete then *g* is equal to the lowest integer greater than or equal to *X*. Consider a number *p* such that the removal of any set of *p* or fewer edges from a complete graph yields a connected graph with *g = X*. The maximum value of *p* is denoted by *NC(v)*.

A graph with vertices *v* is said to be *nearly complete* if it can be constructed by starting with a complete graph with the same number of vertices and removing up to *NC(v)* edges.