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.
Consider a graph with vertices , edges , and genus .
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 .