On the existence of a connected component of a graph

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 ${\mathsf{ACA}}_0$ over ${\mathsf{RCA}}_0$. 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 ${\mathsf{RCA}}_0$ or is equivalent to induction for ${\Sigma }_2^0$ formulas, depending on the formulation of the bound on the number of components.

25 pages, 3 figures. Versions 2 and 3 include additional results related to Weihrauch reducibility

References in corpus (6)

• Closed Choice and a Uniform Low Basis Theorem
• Effective Choice and Boundedness Principles in Computable Analysis
• Weihrauch Degrees, Omniscience Principles and Weak Computability
• On the (semi)lattices induced by continuous reducibilities
• On the strength of the finite intersection principle
• How constructive is constructing measures?

Cited by in corpus (2)

• Primitive recursive reverse mathematics
• Convex choice, finite choice and sorting