Erdős Problem 1067

References:

• erdosproblems.com/1067
• [BoPi24] N. Bowler and M. Pitz, A note on uncountably chromatic graphs. arXiv:2402.05984 (2024).
• [ErHa66] Erdős, P. and Hajnal, A., On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar. (1966), 61-99.
• [Ko13] Komjáth, Péter, A note on chromatic number and connectivity of infinite graphs. Israel J. Math. (2013), 499--506.
• [So15] Soukup, Dániel T., Trees, ladders and graphs. J. Combin. Theory Ser. B (2015), 96--116.
• [Th17] Thomassen, Carsten, Infinitely connected subgraphs in graphs of uncountable chromatic number. Combinatorica (2017), 785--793.

def Erdos1067.InfinitelyEdgeConnected {V : Type u_1} (G : SimpleGraph V) : Prop

A graph is infinitely edge-connected if to disconnect the graph requires deleting infinitely many edges. In other words, removing any finite set of edges leaves the graph connected.

Equations

• Erdos1067.InfinitelyEdgeConnected G = ∀ ⦃s : Set (Sym2 V)⦄, s.Finite → (G.deleteEdges s).Connected

theorem Erdos1067.erdos_1067 : False ↔ ∀ (V : Type) (G : SimpleGraph V), ↑G.chromaticNumber = Cardinal.aleph 1 → ∃ (H : G.Subgraph), ↑H.coe.chromaticNumber = Cardinal.aleph 1 ∧ H.coe.InfinitelyConnected

Does every graph with chromatic number $\aleph_1$ contain an infinitely connected subgraph with chromatic number $\aleph_1$?

Komjáth [Ko13] proved that it is consistent that the answer is no. This was improved by Soukup [So15], who constructed a counterexample using no extra set-theoretical assumptions. A simpler elementary example was given by Bowler and Pitz [BoPi24].

theorem Erdos1067.erdos_1067.variant.infinite_edge_connectivity : False ↔ ∀ (V : Type) (G : SimpleGraph V), ↑G.chromaticNumber = Cardinal.aleph 1 → ∃ (H : G.Subgraph), ↑H.coe.chromaticNumber = Cardinal.aleph 1 ∧ InfinitelyEdgeConnected H.coe

Thomassen [Th17] constructed a counterexample to the version which asks for infinite edge-connectivity (that is, to disconnect the graph requires deleting infinitely many edges).