Ramon Quesada
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
https://wiki.bitcoinsv.io/index.php/Nearly_Complete_Graph
« Back to Glossary Index
