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