1 Answers
In graph theory, an overfull graph is a graph whose size is greater than the product of its maximum degree and half of its order floored, i.e. | E | > Δ ⌊ | V | / 2 ⌋ {\displaystyle |E|>\Delta \lfloor |V|/2\rfloor } where | E | {\displaystyle |E|} is the size of G, Δ {\displaystyle \displaystyle \Delta } is the maximum degree of G, and | V | {\displaystyle |V|} is the order of G. The concept of an overfull subgraph, an overfull graph that is a subgraph, immediately follows. An alternate, stricter definition of an overfull subgraph S of a graph G requires Δ = Δ {\displaystyle \displaystyle \Delta =\Delta }.