Nearly Complete Graph

Revision as of 13:19, 3 May 2020 by Owen Vaughan (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 .

References