Math 2.0

Proposition

Nordhaus–Gaddum inequality

Statement

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

Further reading

  1. Wikipedia, page 47290509, revision 1361633825, Incidence coloring, section Nordhaus–Gaddum inequality. adopted
About this page
TagSNHHPKSZM9
URIm2://SNHHPKSZM9
Kindstatement, proposition
WritingW0 stub
StatusThis copy of the site has no build data. Run m2 status SNHHPKSZM9.
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • edge uses out: each definition that the statement needs (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.