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. where is the size of G, is the maximum degree of G, and 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 .