Connected components of graphs and reverse mathematics (Q2277258)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Connected components of graphs and reverse mathematics |
scientific article |
Statements
Connected components of graphs and reverse mathematics (English)
0 references
1991
0 references
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\).
0 references
decompositions of graphs into connected components
0 references
Statements about infinite graphs
0 references
subsystems of second-order arithmetic
0 references
arithmetical comprehension scheme
0 references
induction scheme
0 references
0 references