Kőnigの線着色定理の証明（ $\chi'(G) = \Delta(G)$）
Kőnigの線の色定理の証明を見つけようとしています。
2部グラフの彩色指数は、その最大次数に等しくなります
しかし、驚いたことに、私はこの主題に触れる2つの質問しか見つけることができませんでした。
- 2部グラフのエッジカラーリング
- 最大次数Dの2部グラフのエッジカラーリングには、Dカラーのみが必要です。
グラフは私のアキレス腱であるため、上記に含まれる情報を使用して証明することはできません $\chi'(G) = \Delta(G)$ 自分。
*それを参照している論文はたくさんありますが、最初の質問のCH6.pdfの4ページを除いて、証明されているものはありませんが、十分ではないと思います。
回答
前提知識の概要を説明し、各ステップでソースを含めて、順番に理解できるようにします。特定の部分（最後の構造など）がわからない場合は、いくつかの小さな例を使用することをお勧めします。
まず、ホールの定理を紹介しましょう。
定理:(ホールの定理） $G$ パーツを含む2部グラフである $A$ そして $B$。次に$G$ 一致する（独立したエッジセット）飽和があります $A$ （のすべての頂点 $A$ マッチングの一部のエッジのエンドポイントです） $X \subseteq A$ 我々は持っています $|X| \le |N(X)|$。
ホールの定理をよく理解するために私がお勧めする2つの情報源は、ディーステルのグラフ理論（思い出すと、4つの証明を与える）とウェストのグラフ理論入門です。
ここでのホールの定理の重要性は、 $k$-通常の2部グラフでは、完全に一致するものを見つけることができます。これは2つのことから来ています：
- A $k$-通常の2部グラフはバランスが取れています。
- A $k$-通常の2部グラフはホールの条件を満たす。
これで、次のことを証明できます。
補題：もし $G$ は $k$-通常の2部グラフ、その後 $\chi'(G) = k$。
誘導を使用できます $k$。ホールの定理により、$G$ 完全に一致しています $M$。検討する$G-M$、これは $k-1$-通常（なぜ？）。帰納法の仮説により、$\chi'(G) = k-1$、そして追加することができます $M$ 新しい色として戻って、適切な拡張 $k-1$-からのエッジカラーリング $G-M$ 適切に $k$-エッジカラーリング $G$。
誘導に慣れていない場合は、別の説明があります。完全一致を削除する $k$-通常の2部グラフは $k-1$-正則グラフ。これも完全に一致している必要があります...このプロセスを繰り返します $k$ 回。
さあ、フィニッシュラインです。私たちは、のために結果を証明したい任意の二部グラフ$G$。
結果：もし $G$ は2部グラフであり、 $\chi'(G) = \Delta(G)$。
場合 $G$定期的である場合、私たちは見出語によって行われます。それ以外の場合は、少なくとも1つの頂点があります$v$ に $G$ と $\deg(v) < \Delta(G)$。グラフを作成できます$R$ そのような
- $R$ 二部です。
- $R$ です $\Delta(G)$-定期的。
- $G \subseteq R$。
1つの構造は次のとおりです。我々は持っています$G$ パーツ付きの2部 $A$ そして $B$。のコピーを取る$G$、 いう $G'$ パーツ付き $A'$ そして $B'$。次に、各頂点について$v$ 程度ではない $\Delta(G)$ に $G$、間にエッジを追加します $v$ そしてそれはコピーです $v' \in G'$。この新しく得られたグラフは、パーツを含む2部グラフです。$A \cup B'$ そして $B \cup A'$。必要に応じてこのプロセスを繰り返します。各反復で最小次数と最大次数の間のギャップが減少することに気付くでしょう。そのため、次数で終了する必要があります。$\Delta(G)$-正則グラフ $R$望んだ通りに。この構造は、JonNoelのコメントによって与えられたものであることがわかります。
見出語を使用して、 $\chi'(R) = \Delta(G)$、したがって、適切な $\Delta(G)$-のエッジカラーリング $R$。以来$G \subseteq R$、この適切な色付けは $G$。つまり、$\chi'(G) = \Delta(G)$。
いくつかのメモ。
一般的な事実を使用したことに注意してください $\chi'(H) \le \chi'(G)$ ために $H \subseteq G$ 最後に。
私が一瞥したことの1つは、複数のエッジを許可するかどうかですが、それでも問題はありません。複数のエッジを許可する場合、なぜ私たちが構築した方法がわかりますか$R$ 正確にかかります $1$反復？複数のエッジの使用を除外する本当の理由はないと思います。
重要なポイントの1つは、エッジカラーリングのカラークラスをそれらが何であるか、つまりマッチングと考えることです。