On the existence of a connected component of a graph

الأصل · EN

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 ACA₀ over RCA₀. 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 RCA₀ or is equivalent to induction for Σ⁰₂ formulas, depending on the formulation of the bound on the number of components.