Not a Certificate for Bounded Graphs: a Counterexample to a Conjecture of Thomassen

Reinhard Diestel and Imre Leader

An infinite graph is called bounded if for every labelling of its vertices with natural numbers there exists a sequence of natural numbers which eventually exceeds the labelling along any ray in the graph. Thomassen has conjectured that a countable graph is bounded if and only if its edges can be oriented, possibly both ways, so that every vertex has finite out-degree and every ray has a forward oriented tail. We present a counterexample to this conjecture.

1. The conjecture

For two ℕ → ℕ functions f and g, let us say that f dominates g if f(n) ⩾ g(n) for every n greater than some n_{0} ^{∈} ℕ.

An infinite graph G is called bounded if for every labelling of its vertices with natural numbers there is an ℕ → ℕ function which dominates every labelling along a ray (one-way infinite path) in G. More precisely, G is bounded if for every labelling ℓ: V (G) → ℕ there is a function f: ℕ → ℕ such that for every ray x_{0}x_{1} … in G the function n ↦ ℓ(x_{n}) is dominated by f. Otherwise G is unbounded.

Let us see some examples of bounded or unbounded graphs.

Every locally finite connected graph is bounded. Indeed, given a labelling ℓ, and given any fixed vertex v of G, it is easy to define a function f_{v} which dominates all the rays starting at v: just take as f_{v}(n) the largest label of the vertices at distance at most n from v. Now G has only countably many vertices, so there are only countably many functions f_{v}, say f^{0}, f^{1}, . . .. Setting f(n) = max _{i⩽n}f^{i}(n), we obtain a function f: ℕ → ℕ which dominates every f_{v}, and hence dominates every ray in G.

The complete graph on a countably infinite set of vertices, K_{ω}, is clearly unbounded: just choose any labelling that uses infinitely many distinct labels, and there will be rays whose labellings grow faster than any fixed ℕ → ℕ function. The regular tree of countably infinite degree, T_{ω}, is another simple example of an unbounded graph: just label its vertices injectively, i.e. so that any two labels are different.

Two further examples for unboundedness are found in the graphs B and F shown in Fig. 1; again, any injective labelling will show that these graphs are unbounded.

Bounded graphs were first introduced by R. Halin around 1964, in connection with R. Rado’s well-known paper on Universal graphs and universal

FIGURE 1. The unbounded graphs B and F

functions [ 4 ]. Halin conjectured that a countable graph is bounded if and only if it has no subgraph isomorphic to a subdivision of any of the three graphs T_{ω}, B and F. Halin himself proved this for some special cases [ 2–3 ]; the conjecture was recently proved by the authors [ 1 ]. (We remark that [ 1 ] also contains an uncountable version of this result. In the present paper, however, we are only interested in countable graphs.)

An interesting aspect of this ‘bounded graph theorem’, typical for a characterization by forbidden configurations, is that it provides us with simple ‘certificates’ for unboundedness: all we need do to convince someone of the unboundedness of a particular countable graph is to exhibit in it one of the three types of forbidden subgraph. For boundedness, by contrast, no such ‘certificates’ are known.

C. Thomassen has recently proposed the following attractive conjecture, which would have provided not only another elegant characterization of the bounded graphs but also something like a certificate for boundedness:

Conjecture. (Thomassen) A countable graph is bounded if and only if its edges can be oriented, each in one or both or neither of its two directions, so that every vertex has finite out-degree and every ray has a forward oriented tail.

(A tail of a ray x_{0}x_{1} … is a subray x_{n}x_{n+1} …, and it is forward oriented if every edge x_{m}x_{m+1} (m ⩾ n) is oriented from x_{m} towards x_{m+1} (and possibly, but not necessarily, also from x_{m+1} towards x_{m}).)

An orientation as above will be called admissible. We remark that any admissible orientation can be extended to one in which every edge has at least one direction: since the graph has only countably many vertices, v_{0}, v_{1}, … say, local finiteness will be preserved if every unoriented edge v_{i}v_{j} with i < j is oriented from v_{j} to v_{i}.

Intuitively, an admissible orientation identifies in the graph a locally finite substructure mapping out the preferred directions of rays: eventually, every ray in the graph will follow a ray indicated by the orientation. Much of the attractiveness of Thomassen’s conjecture lies in its promise that the boundedness of any bounded graph can be tied to such a definite and simple substructure— one that is obviously itself bounded (by local finiteness) and at the same time accounts for the boundedness of the entire graph.

The ‘if’ direction of Thomassen’s conjecture is clearly true: to prove it, we just imitate the proof that locally finite connected graphs are bounded. More precisely, given an admissible orientation of the graph and any labelling of its vertices, we first find a function f that dominates every forward oriented ray (as in our local finiteness proof); the function g defined by

g: n ↦ f(1) + … + f(2n)

then dominates every ray in the graph.

Note also that the conjecture is trivially true for locally finite graphs themselves, as we may simply orient every edge both ways. The provision for 2-way orientations in the definition of admissible is, however, essential: the infinite ladder is an example of a bounded graph whose edges cannot be 1-way oriented in such a way that every ray has a forward oriented tail.

Finally, it is not difficult to prove the conjecture for trees; this was first observed by Thomassen [ 5 ].

Unfortunately, Thomassen’s conjecture is not true in general: in the next section we shall exhibit a graph which is bounded but allows no admissible orientation of its edges.

2. The counterexample

Let S be the graph constructed as follows (see Fig. 2). For every n ^{∈} ℕ, let R^{n} = v_{0}^{n}v_{1}^{n}v_{2}^{n} … be a ray. Let these rays be pairwise disjoint, except that v_{0}^{n} = v_{n}^{0} for every n. For every odd n, make the pair (R^{n}, R^{n+1}) into a ladder by adding the edges v_{i}^{n}v_{i}^{n+1} for all i > 0, as rungs. Finally, for every even n > 0, add a new vertex x^{n} and join it to every vertex of R^{n} except v_{0}^{n}.

FIGURE 2. The graph S

Theorem. The graph S is bounded but allows no admissible orientation of its edges.

Proof. It is not difficult to see that the edges of S cannot be admissibly oriented. Indeed, as the vertices x^{n} all have infinite degree, any admissible orientation would leave each x^{n} incident with an edge e^{n} = x^{n}v_{i}^{n} (for some i) that is not oriented from x^{n} towards v_{i}^{n}. It is then easy to find a ray in S which traverses every such edge e^{n} from x^{n} towards v_{i}^{n}, i.e. against its (possible) orientation.

It remains to show that S is bounded. Using the abovementioned bounded graph theorem, all we need to show is that S contains no subdivision of T_{ω}, B or F. This is easily done. The cases of T_{ω} and B are trivial. Now suppose we have embedded a subdivision of F into S. The bottom ray of F will then be mapped to a ray R ⊂ S which contains infinitely many of the vertices x^{n}, since these are the only vertices of S that have infinite degree. For each of those n (except possibly the first), the initial segment Rx^{n} of R separates its tail x^{n}R from all but finitely many neighbours of x^{n} in S. As this is not the case for the bottom ray and the vertices of infinite degree in F, we have a contradiction. □

Actually, is not much more difficult to verify the boundedness of S directly. Let ℓ: V (G) → ℕ be a labelling of S; we shall define a function f: ℕ → ℕ that dominates every ray in S with respect to ℓ. Let g and f be defined by

g: n ↦ ∑_{i,j⩽n}(ℓ(x_{2i+2}) + ℓ(v_{j}^{i}))  and  f: n ↦ g(2n).

Note that g is increasing and dominates every R^{n}. Therefore f dominates every ray that has a tail in

S′ = S − { x_{2}, x_{4}, … }.

Now let R be an arbitrary ray in S. If R has a tail in S′, then f dominates R. Otherwise, R contains infinitely many x^{n}. It is easily seen that g dominates any ray that starts at v_{0}^{0} and contains infinitely many x^{n}. Since R contains a tail of such a ray, it follows that f dominates R.

Naturally, the question arises as to which graphs can be admissibly oriented. To give this property a proper name (at last), let us say that a countable graph is finitely spreading if its edges can be admissibly oriented. Thus finitely spreading graphs are bounded, but not vice versa.

There are indications that our graph S may be essentially the only bounded graph which is not finitely spreading. More precisely, we suspect that every bounded graph which is not finitely spreading contains a subdivision of the graph S′ of Fig. 3. (Note that S contains a subdivision of S′, but not conversely.) By the bounded graph theorem, this is equivalent to the following conjecture:

Conjecture. A countable graph is finitely spreading if and only if it has no subgraph isomorphic to a subdivision of any of the four graphs T_{ω}, B, F, S′.

FIGURE 3. The unique minimal counterexample?

References

[ [ 1 ]] R. Diestel and I. Leader, A proof of the bounded graph conjecture, Invent. math. (to

appear). [ [ 2 ]] R. Halin, Some problems and results in infinite graphs, in: (L.D. Andersen et al., Eds.)

Graph Theory in Memory of G. A. Dirac (Annals of Discrete Mathematics 41), North-Holland Publ. Co., Amsterdam/London 1989.

[ [ 3 ]] R. Halin, Bounded graphs, in: (R. Diestel, Ed.) Directions in infinite graph theory and

combinatorics (Annals of Discrete Mathematics), in press. [ [ 4 ]] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340. [ [ 5 ]] C. Thomassen, private communication.

Reinhard Diestel

Faculty of Mathematics (SFB 343)

Bielefeld University D-4800 Bielefeld Germany Imre Leader Department of Pure Mathematics 16 Mill Lane Cambridge CB2 1SB England