One curiosity that in the case of infinite graphs, "no odd cycles" doesn't imply "2-colorable" without the axiom of choice for families of 2-element sets [0]. It's somewhat similar to how in the definition of a well-founded relation, "no infinite descending chains" doesn't imply "every nonempty subset has a minimal element" without dependent choice.

(One of my recent projects has been trying to prove the existence of a 2-colorable subgraph for a certain class of infinite graphs in ZF, which has led me surprisingly deep into choice principles and models refuting them.)

[0] https://mathoverflow.net/a/453944