---
tag: SNHHPKSZM9
kind: statement
role: proposition
name: Nordhaus–Gaddum inequality
sources:
  - wikipedia: en:47290509@r1361633825
    locator: Incidence coloring, section Nordhaus–Gaddum inequality
    note: adopted
    mention: wikipedia://en/47290509#BARB
    sections: [Statement]
inventory: [MPG5FC5G0Q]
---

## Statement

Let *G* be a graph with *n* vertices such that $G\neq K_n, \overline{K_n}$ where $\overline{G}$ denotes the complement of *G*. Then $n + 2 \leq \chi_i(G) + \chi_{i}(\overline{G})\leq 2n-1.$ These bounds are sharp for all values of *n*.