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.


« Back to Glossary Index

Written by Ramon Quesada

Passionate about Blockchain & Bitcoin technology since 2013, Co- Founder of, Team Manager in the CoinTelegraph Spain franchise (2016-2017 years) Co. Organizer of the Blockchain Boot camp Valencia 2018, Co. Organizer of the mini Hackathon BitcoinSV Barcelona, in August 2019, current coordinator of the BSV Valencia Meetup.

Nakamoto Consensus *