---
tag: MH8R6VYK7S
kind: concept
name: Overfull graph
aliases: [overfull-conjecture]
sources:
  - wikipedia: en:23472134@r1317723716
    locator: Overfull graph
    note: adopted
    mention: wikipedia://en/23472134
    sections: [Summary]
same_as:
  wikidata: Q7113657
  wikipedia: Overfull graph
inventory: [EN50Q7N1AF]
---

## Summary

In graph theory, an **overfull graph** is a [[graph|00C0BR7D7H]] whose [[size|00C0BR7D7H]] is greater than the product of its maximum [[degree|0KS0KRDV4Y]] and half of its [[order|00C0BR7D7H]] 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)$.