Overfull graph

Summary

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| > \Delta (G) \lfloor |V|/2 \rfloor$ where $|E|$ is the size of G, $\displaystyle\Delta(G)$ is the maximum degree of G, and $|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\Delta (G) = \Delta (S)$.