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

    Identifiers