Quickly proving Diestel's normal spanning tree criterion (Q820854)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 7402038
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Quickly proving Diestel's normal spanning tree criterion |
scientific article; zbMATH DE number 7402038 |
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.838826596736908
0 references
0.8358762264251709
0 references
0.7921721339225769
0 references
0.7788739800453186
0 references
0.7730190753936768
0 references
