![](/files/happy5.png)
Call a graph an -graph if it has a bipartition
so that every vertex in
has degree
and every vertex in
has degree
.
![$ (\aleph_0,\aleph_1) $](/files/tex/4170402299493c216234845dcc59a455da96e488.png)
The motivation for this problem comes from a lovely paper of Diestel and Leader [DL] where they prove that an infinite graph has a normal spanning tree (the natural infinite analogue of a depth-first search tree) if and only if it has no minor isomorphic to either an -graph or an Aronszajn tree. (An earlier conjecture of Halin asserted that only the first of these excluded minors was needed.) So,
-graphs appear as a forbidden minor obstruction to the existence of a kind of depth-first search tree for infinite graphs.
The obvious example of an -graph is
, but there are other natural families of such graphs. For instance, let
be an infinite binary tree with root
, and let
be the set of all rays (one way infinite paths) with endpoint
. Now, form a bipartite graph with vertex bipartition
and adjacency given by the rule that
adjacent to
if and only if
lies on the ray
(in
). Any
-graph which is isomorphic to a subgraph of this graph is said to be of binary type.
Say that a -graph is divisible if there exist disjoint subsets
and disjoint subsets
so that the graphs induced by both
and
are
-graphs. It is not difficult to show that every binary type graph is divisible. Curiously, the existence of non-divisible
-graphs depends on the Continuum Hypothesis (see [DL]).
Although it is not clear wether or not there is a nice characterization of -graphs, it would certainly be interesting to find more natural families of these graphs. The following rather more concrete question is posed by Diestel and Leader who suspect the answer is 'no'.
![$ (\aleph_0,\aleph_1) $](/files/tex/4170402299493c216234845dcc59a455da96e488.png)
![$ (\aleph_0,\aleph_1) $](/files/tex/4170402299493c216234845dcc59a455da96e488.png)
Bibliography
[DL] R. Diestel and I. Leader, Normal spanning trees, Aronszajn trees and excluded minors, J. London Math. Soc. 63 (2001), 16-32;
* indicates original appearance(s) of problem.