3 ms·
Use the subgraph relation to define the poset. The big graph is then obviously an upper bound for every chain.
by actually_a_dog 4y ago
Use the subgraph relation to define the poset. The big graph is then obviously an upper bound for every chain.
- Chinjut 4y agoYes, but invoking Zorn's lemma on that poset does nothing useful. This just proves the trivial fact that the big graph exists. How do you prove that a coloring of the big graph exists? And if we take the poset to be partial colorings ordered by inclusion, it's not the case that a maximal partial coloring must color the entire graph. Some partial colorings have made choices which prevent them from being extended any further. [To be clear, whenever I say "coloring", I mean from a fixed set of colors. E.g., a 4-coloring.]
- Chinjut 4y agoPut another way, it actually is important here that the set of colors we are talking about is finite. It's NOT the case that just having every finite subgraph be C-colorable entails that the entire graph is C-colorable, when C is infinite. For example, if G is the complete graph on an uncountable set of nodes and C is a countably infinite set, then every finite subgraph of G is C-colorable, but G itself is not. So somewhere in the argument, the finiteness of C must play a role. This is in ensuring compactness.