Affiliations: Department of Mathematics, Marshall University, 1 John Marshall Drive, Huntington, WV 25755, USA. [email protected] | Department of Mathematical Sciences, Appalachian State University, Walker Hall, Boone, NC 28608, USA. [email protected] | Department of Mathematics, Marshall University, 1 John Marshall Drive, Huntington, WV 25755, USA. [email protected]
Abstract: We study the reverse mathematics and computability of countable graph theory, obtaining the following results. The principle that every countable graph has a connected component is equivalent to ACA0 over RCA0. The problem of decomposing a countable graph into connected components is strongly Weihrauch equivalent to the problem of finding a single component, and each is equivalent to its infinite parallelization. For graphs with finitely many connected components, the existence of a connected component is either provable in RCA0 or is equivalent to induction for Σ20 formulas, depending on the formulation of the bound on the number of components.
