On the existence of a connected component of a graph
Kirill Gura, Jeffry L. Hirst, Carl Mummert · Computability · 2015
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 [Formula: see text] over [Formula: see text]. 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 [Formula: see text] or is equivalent to induction for [Formula: see text] formulas, depending on the formulation of the bound on the number of components.