Quickly proving Diestel's normal spanning tree criterion (Q820854)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Quickly proving Diestel's normal spanning tree criterion
scientific article

    Statements

    Quickly proving Diestel's normal spanning tree criterion (English)
    0 references
    28 September 2021
    0 references
    This paper deals with the proofs for Diestel's criterion that a connected graph has a normal spanning tree provided it contains no subdivision of a countable clique in which every edge has been replaced by uncountably many parallel edges. The author presented two proofs of the mentioned criterion. The first of them is by induction on the number of vertices of the graph. The second proof extracts the closure properties defined in the first proof, and combines them into a single algorithm constructing the normal spanning tree. The techniques used in the two proofs are not easy but they are good proofs and give us algorithms for this problem.
    0 references
    Diestel's criterion
    0 references
    0 references

    Identifiers