濃度については順序数・濃度の簡単なまとめも参照．

定義 V が集合， E が V 上の二項関係で非反射的かつ反対称的なとき，組 G=(V, E) をグラフという．

定義 G=(V, E) をグラフとする．

1. S⊂V が従属(dependent) ⇔ ある x, y∈S が存在して xEy となる．
2. S⊂V が独立(independent) ⇔ S が従属でない．
3. 写像 f: V→C が「任意の c∈C に対して f^-1(c)⊂V が独立である」を満たすとき， f を彩色(coloring)と呼ぶ．
4. 彩色 f: V→C が存在するとき， G は |C|-彩色可能であるという．
5. χ(G) := min{ λ | G は λ-彩色可能である } が存在するとき，χ(G) を G の彩色数(chromatic number)という．
6. f: V→C が既約(irreducible) ⇔ 任意の c, d∈C，c≠d に対して f^-1(c)∪f^-1(d) が従属となる．

定義 集合 X, Y に対してグラフ G(X, Y)=(X×Y, E₀) と G'(X, Y)=(X×Y, E₁) を次により定める．

<x, y>E₀<x', y'> ⇔ (x=x', y≠y')または(x≠x', y=y')
<x, y>E₁<x', y'> ⇔ x≠x'かつy≠y'

定理1 次の命題は( ZF 上)同値．

1. 選択公理
2. 任意のグラフの彩色数が存在する．
3. 任意の集合 X に対して，グラフ G'(X, Γ(X)) の彩色数が存在する．

証明 (1 ⇒ 2)彩色は任意のグラフに対して存在するから，選択公理により最小元 χ(G) = min{ λ | G は λ -彩色可能である } も存在する．

(2 ⇒ 3) 明らか．

(3 ⇒ 1) グラフ G := G'(X, Γ(X)) は |X|-彩色可能かつ |Γ(X)|-彩色可能である．故に χ(G)≦|X| かつ χ(G)≦|Γ(X)| となる． χ(G)=|Γ(X)| と仮定すると |Γ(X)|=χ(G)≦|X| となり矛盾するから， χ(G) < |Γ(X)| である．

|C|=χ(G) となる集合 C と彩色 f: X×Γ(X)→C を取る． |C| < |Γ(X)| だから C は整列順序集合としてよい．x∈X，c∈C に対して A(x, c) := { α∈Γ(X) | f(x, α)=c } と置く．任意の x∈X に対してある c∈C が存在して |A(x, c)|≧2 となる．

よって g(x) := min{ c∈C | |A(x, c)|≧2 } と定義することができる．この g: X→C は単射である．

故に |X|≦|C| となり X は整列可能である．

証明から，次の同値も成り立つことが分かる．

定理2 選択公理 ⇔ グラフ G が λ₀-彩色可能かつ λ₁-彩色可能ならば，ある基数 μ が存在して μ≦λ₀，μ≦λ₁ かつ G がμ-彩色可能となる．

更に，次も成り立つ．

定理3 選択公理 ⇔ グラフ G が λ₀-彩色可能かつ λ₁-彩色可能ならば，ある基数 μ が存在して μ≦^*λ₀，μ≦^*λ₁ かつ G がμ-彩色可能となる．

証明 ( ⇒ ) 明らか．

( ⇐ ) X を集合とする．グラフ G'(X, Γ(P(X))) は |X|-彩色可能かつ |Γ(P(X))|-彩色可能だから，仮定により，ある基数 λ が存在して， λ≦^*|X|，λ≦^*|Γ(P(X))| かつ G'(X, Γ(P(X))) が λ-彩色可能である． λ < |Γ(P(X))| となる．

よって定理1の 3⇒1 の証明と同様にして X が整列可能であることがわかる．

定理4 次の命題は( ZF 上)同値．

1. 選択公理
2. 任意のグラフは既約な彩色を持つ．
3. 任意の集合 X に対して，グラフ G(X, Γ(X)) は既約な彩色を持つ．

証明 (1 ⇒ 2) (V, E) をグラフとする． V の整列順序 ≦ を取る． f: V→V を f(x) := min(V＼{ f(y) | y<x, yEx }) で定めれば f は既約な彩色である．

(2 ⇒ 3) 明らか．

(3 ⇒ 1)無限集合 X が整列可能であることを示す．仮定3より， G(X, Γ(X)) の既約な彩色 f: X×Γ(X)→C が存在する． π₁: X×Γ(X)→X，π₂: X×Γ(X)→Γ(X) を標準射影とする．c₀∈C を一つ取り， M := f^-1(c₀)，S₁ := π₁(M)×Γ(X)，S₂ := X×π₂(M)，C₁ := f(S₁)，C₂ := f(S₂) と定める．

f は彩色だから， c∈C に対して π₁|_f^-1(c),π₂|_f^-1(c) は単射である．よって |π₁(M)|=|f^-1(c₀)|=|π₂(M)| となる．また |f^-1(c)|≦|Γ(X)| となり， f^-1(c) に整列順序が入る．よって S⊂X×Γ(X) に対して写像 g: f(S)→S を g(c):=min(S∩f^-1(c)) で定めることができる．この g は明らかに単射である．故に |f(S)|≦|S| となる．従って |C₁|=|f(S₁)|≦|S₁|=|π₁(M)×Γ(X)| となり C₁ も整列順序が入る．また

|C₂|=|f(S₂)|≦|S₂|=|X×π₂(M)|=|X×π₁(M)|≦|X×X|

となる． Γ(X)=Γ(X×X) だから， |Γ(X)||C₂| である．一方， x∈X に対して Γ(X)∋α|→f(x, α)∈C は単射である．故に A_x := { <w, c>∈Γ(X)×C₁ | f(x, α)=c } ≠ ∅ となる．Γ(X)，C₁ は整列されているから h: X→Γ(X)×C₁ を h(x) := min(A_x) で定めることができる．この h は単射だから X も整列可能である．