Connected components of graphs and reverse mathematics (Q2277258)

Statements about infinite graphs can be formalized in the language of Friedman and Simpson's subsystems of second-order arithmetic. Working in \(RCA_ 0\), the following results concerning decompositions of graphs into (maximal) connected components can be proved. The statement ``every graph can be decomposed into its connected components'' is equivalent to the arithmetical comprehension scheme, \(ACA_ 0\). The statement ``for each \(k\in {\mathbb{N}}\), every graph with at most k connected components can be decomposed into its connected components'' is equivalent to the induction scheme \(I\Sigma^ 0_ 2\).