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 - 3v + 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.


References