An end-faithful spanning tree counterexample

Paul Seymour; Robin Thomas

doi:10.1016/0012-365X(91)90344-2

An end-faithful spanning tree counterexample

Paul Seymour, Robin Thomas

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

We find an infinitely-connected graph in which every spanning tree has a 2-way infinite path. This disproves Halin's well-known 'end-faithful spanning tree' conjecture, and also disproves a recent conjecture of Širáň.

Original language	English (US)
Pages (from-to)	321-330
Number of pages	10
Journal	Discrete Mathematics
Volume	95
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(91)90344-2
State	Published - Dec 3 1991
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(91)90344-2

Cite this

@article{8ac917f4f58f466cb7955fb603cd0bdc,

title = "An end-faithful spanning tree counterexample",

abstract = "We find an infinitely-connected graph in which every spanning tree has a 2-way infinite path. This disproves Halin's well-known 'end-faithful spanning tree' conjecture, and also disproves a recent conjecture of {\v S}ir{\'a}{\v n}.",

author = "Paul Seymour and Robin Thomas",

year = "1991",

month = dec,

day = "3",

doi = "10.1016/0012-365X(91)90344-2",

language = "English (US)",

volume = "95",

pages = "321--330",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - An end-faithful spanning tree counterexample

AU - Seymour, Paul

AU - Thomas, Robin

PY - 1991/12/3

Y1 - 1991/12/3

N2 - We find an infinitely-connected graph in which every spanning tree has a 2-way infinite path. This disproves Halin's well-known 'end-faithful spanning tree' conjecture, and also disproves a recent conjecture of Širáň.

AB - We find an infinitely-connected graph in which every spanning tree has a 2-way infinite path. This disproves Halin's well-known 'end-faithful spanning tree' conjecture, and also disproves a recent conjecture of Širáň.

UR - http://www.scopus.com/inward/record.url?scp=0039397837&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039397837&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(91)90344-2

DO - 10.1016/0012-365X(91)90344-2

M3 - Article

AN - SCOPUS:0039397837

SN - 0012-365X

VL - 95

SP - 321

EP - 330

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

An end-faithful spanning tree counterexample

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this