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.


Leave a Reply

Your email address will not be published. Required fields are marked *



Nakamoto Consensus *