Every rayless graph has an unfriendly partition

Henning Bruhn Reinhard Diestel ∗Agelos Georgakopoulos^{∗} Philipp Sprüssel

Mathematisches Seminar Universität Hamburg

Bundesstr. 55, 20146, Germany

12 December, 2009

Abstract We prove that every rayless graph has an unfriendly partition.

1 Introduction

A bipartition of the vertex set of a graph is unfriendly if every vertex has at least as many neighbours in the other class as in its own. The following conjecture is one of the best-known open problems in infinite graph theory.

Unfriendly Partition Conjecture. Every countable graph admits an unfriendly partition of its vertex set.

Clearly, every finite graph has an unfriendly partition: just take any bipartition that maximizes the number of edges between the partition classes. For infinite graphs however, few results are known. Shelah and Milner [4] constructed uncountable graphs that admit no unfriendly partitions, thereby disproving the original folklore conjecture that every graph has an unfriendly partition. (They attribute this conjecture to R. Cowan and W. Emerson, unpublished.) It is an easy exercise in compactness to deduce from the finite theorem that every locally finite graph has an unfriendly partition, see [2]. Aharoni, Milner and Prikry [1] strengthened this fact by proving that every graph with only finitely many vertices of infinite degree has an unfriendly partition.

At the other end of the spectrum, it is easy to prove that countable graphs in which only finitely many vertices have finite degree have unfriendly partitions. Since the counterexamples from [4] have no vertices of finite degree, the countability assumption here cannot be dropped.

The main aim of this paper is to prove that all rayless graphs, countable or not, have unfriendly partitions:

Theorem 1.1. Every rayless graph has an unfriendly partition.

∗Supported by a GIF grant.

For the proof of this theorem we used a tool developed by Schmidt [3], which assigns to every rayless graph an ordinal number, its rank. This rank enables us to prove Theorem 1.1 by transfinite induction.

Closer inspection of the proof reveals that it does not depend on the graphs being rayless, but only on the existence of such a kind of rank. Extending the method to more general rank functions, one can indeed strengthen Theorem 1.1 in various ways. One such strengthening obtained in Section 4 is this:

Theorem 1.2. Every graph not containing a ray linked disjointly to infinitely many vertices of infinite degree has an unfriendly partition.

2 Definitions and statement of main result

Recall that a cofinal subset of an ordered set A is a subset B such that for every a ∈ A there is a b ∈ B such that a ≤ b. The cofinality of an ordinal α is the smallest ordinal δ which is the order type of a cofinal subset of α. The cofinality of an ordinal is always a cardinal, but we will not need to make use of this fact.

For general graph-theoretic terminology we refer the reader to [2]. Given a graph G and a vertex x ∈ V (G), we let d_{U}(x) denote the number of neighbours of x in a subset U ⊆ V (G). For convenience, if C is a subgraph of G, or a set of subgraphs of G, or a set of sets of subgraphs of G, we will simply write d_{C}(x) —to avoid more cumbersome notation of the form d_{V (⋃ C)}(x)— for the number of neighbours of x (nested) in C.

A partition of a set V or a graph G = (V, E) is a function π : V → {0, 1}. For a partition π of G and a vertex x ∈ V (G), we say that a neighbour y of x is an opponent (respectively, a friend) of x in π if π(y) ≠ π(x) (resp. π(y) = π(x)). We write a_{π}(x) for the number of opponents of x in π. Moreover, if U is a subset of V (G) or a subgraph of G, then we write a_{π}(x, U) for the number of opponents of x in π that lie in U. A vertex is happy in a partition π if it has at least as many opponents as it has friends. In particular, if a vertex x has infinite degree then it is happy in π if and only if d(x) = a_{π}(x). A partition is unfriendly if every vertex is happy in it, and it is unfriendly for a vertex set Y if every vertex in Y is happy.

A graph G is pre-partitionable if for every U ⊆ V (G) and every partition π of U there is a partition π′ of G extending π so that every vertex in V (G)\U is happy in π′. In particular, since we can choose U to be the empty set, every pre-partitionable graph has an unfriendly partition. Clearly, every finite graph is pre-partitionable: given U and π, choose π′ so as to maximize the number of edges incident with V (G) \ U whose endvertices lie in different partition classes.

Schmidt [3] observed that it is possible to construct all rayless graphs by a recursive, transfinite procedure, starting with the class of finite graphs and then, in each step, glueing graphs constructed in previous steps along a common finite vertex set, to obtain new rayless graphs. We are going to generalise Schmidt’s construction by replacing the class of finite graphs by larger classes.

In order to do so, we call a class U of graphs finitely closed if it is closed under taking finite disjoint unions and also under adding finitely many new vertices and joining them arbitrarily to each other and to the old vertices. Starting with any finitely closed class U it is possible to recursively construct a larger class \overline{U} as follows.

Definition 2.1. Let U be a finitely closed class of graphs. For every ordinal μ we define recursively a class U(μ):

• U(0) := U; and

• if U(λ) is defined for every λ < μ, we include a graph G in U(μ) if it has a finite vertex set S such that for every component C of G − S there is an ordinal λ < μ such that U(λ) contains C.

The closure \overline{U} of U is the union of the classes U(λ) for all ordinals λ. For a graph G in \overline{U} we define its rank to be the smallest ordinal r_{U}(G) = r(G) such that U(r(G)) contains G.

The prime example of a finitely closed class is the class F of finite graphs, and the rayless graphs are precisely those in \overline{F} [3]. The locally finite graphs clearly do not form a finitely closed class; but the graphs with only finitely many vertices of infinite degree do, and so do the graphs with only finitely many vertices of finite degree. Another class, which contains all these, will be defined in Section 4.

We note two properties of the above construction that are not hard to prove.

Lemma 2.2. Let G be a graph in \overline{U} for some finitely closed class U of graphs, and let S be a finite vertex set so that r(C) < r(G) for every component C of G − S.

(i) If C_{1}, …, C_{n} are components of G − S then r(G[S ∪ ⋃_{i=1}^{n} C_{i}]) < r(G).

(ii) If S is ⊆-minimal with the property that r(C) < r(G) for each component C of G − S then each vertex in S has infinite degree.

Proof. To see (i), we show that r(G[S ∪ ⋃_{i=1}^{n} C_{i}]) ≤ max_{i} r(C_{i}) which is by assumption smaller than r(G). Suppose first that all C_{i} have rank 0, i.e. lie in U. Then so does G[S ∪ ⋃_{i=1}^{n} C_{i}] as U is finitely closed. Otherwise, for every 1 ≤ i ≤ n with r(C_{i}) > 0 let S_{i} be a finite vertex set in C_{i} such that the rank of every component of C_{i} − S_{i} is less than r(C_{i}). Then S ∪ ⋃ S_{i} is a finite set witnessing the fact that r(G[S ∪ ⋃_{i=1}^{n} C_{i}]) ≤ max_{i} r(C_{i}).

For (ii), note that if x ∈ S has finite degree then the components of G − (S \ {x}) are precisely the components of G − S that are not adjacent to x, plus one new component obtained by merging x and the finitely many components of G − S adjacent to x. By an argument similar to that of (i), the rank of this new component is at most the maximum of the ranks of the components that got merged. But then r(C) < r(G) for every component C of G − (S \ {x}), contradicting the minimality of S with this property.

Here is the main result of this paper:

Theorem 2.3. If U is a finitely closed class of graphs and every graph in U is pre-partitionable, then every graph in \overline{U} is pre-partitionable.

As every finite graph is pre-partitionable and every pre-partitionable graph has an unfriendly partition, Theorem 2.3 with U = F implies Theorem 1.1.

We prove Theorem 2.3 in Section 3. In Section 4 we use it to prove that a considerably larger class than the rayless graphs have unfriendly partitions.

3 Proof of the main result

We now prove Theorem 2.3.

Proof of Theorem 2.3. Let G = (V, E) be a graph in \overline{U}. We perform transfinite induction on r(G). If r(G) = 0 then G is pre-partitionable by assumption, so suppose that r(G) = α > 0 and the assertion is true for all ordinals β < α. Let S ⊆ V (G) be a minimal separator such that r(C) < α for every component of G − S, and let C be the set of those components. We will prove that G is pre-partitionable by a second transfinite induction on κ := |C|. By Lemma 2.2, κ must be infinite. We will treat the first step of the induction (i.e. the case κ = ω) more or less in the same way as the induction step; so assume from now on that either κ = ω or κ > ω and, by the induction hypothesis, any subgraph of G spanned by S and less than κ elements of C is pre-partitionable; by Lemma 2.2, we can assume this even if κ = ω.

Let S_{0} be the set of vertices s ∈ S for which there is a subset C_{s} of C of cardinality less than κ with d_{C_{s}}(s) = d(s); then let S_{1} := S\S_{0}. Let X_{0} := ⋃_{s∈S_{0}} C_{s}, and assume, without loss of generality, that

N(s) ⊆ S ∪ ⋃ X_{0} for every s ∈ S_{0} with d(s) < κ,  (1)

where N(s) denotes the set of vertices adjacent with s.

We claim that

if s ∈ S_{1} then either d(s) = κ or d(s) is a singular cardinal of cofinality

κ. (2)

Indeed, all vertices in S with degree less than κ lie in S_{0}, thus d(s) ≥ κ. If s has degree λ > κ then λ is a singular cardinal of cofinality at most κ as it is the sum of κ cardinals smaller than λ, namely of d_{C}(s) for all C ∈ C (we know that d_{C}(s) < λ because s ∉ S_{0}). It remains to verify that the cofinality of λ is not smaller than κ.

Suppose, on the contrary, that λ is the sum of cardinals β_{α}, α < γ, where γ < κ and every β_{α} is smaller than λ. Then for every α there is a component C^{α} ∈ C such that d_{C^{α}}(s) ≥ β_{α}; for if not, then λ ≤ |C| · β_{α} < λ, a contradiction. But then, the components C^{α}, α < γ contain λ = d(s) many of the neighbours of s, and as γ < κ this contradicts s ∉ S_{0}.

It is possible to partition C\X_{0} into κ finite sets X_{β}, β < κ so that

for every s ∈ S_{1} and every subset Z of {X_{β}}_{β<κ} with |Z| = κ there

holds d_{Z}(s) = d(s). (3)

Indeed, given s ∈ S_{1}, it is easy, in both cases of (2), to find a sequence (C_{β}^{s})_{β<κ} of distinct elements of C such that for every subset Z′ of {C_{β}^{s} | β < κ} with |Z′| = κ there holds d_{Z′}(s) = d(s). Furthermore, let (D_{β})_{β<λ} be a sequence indexed by some ordinal λ ≤ κ containing all elements D of C that are not in a sequence (C_{β}^{s})_{β<κ} for any s ∈ S_{1}. Depending on whether κ = ω or not, we now define the X_{i}, i < κ, recursively as follows. If κ > ω, then for every s ∈ S_{1} we let C_{m_{i}}^{s} be the first member of (C_{β}^{s})_{β<κ} that is not an element of ⋃_{β<i} X_{β}, and let X_{i} := {D_{i}} ∪ {C_{m_{i}}^{s} | s ∈ S_{1}} if i < λ and X_{i} := {C_{m_{i}}^{s} | s ∈ S_{1}} otherwise. If κ = ω, we define X_{i} in a slightly different way. Namely, we let X_{i} := {D_{i}}∪⋃_{s∈S_{1}} C_{i}^{s} if i < λ and X_{i} := ⋃_{s∈S_{1}} C_{i}^{s} otherwise, where C_{i}^{s} is a finite subset of {C_{β}^{s}}_{β<κ}\ ⋃_{β<i} X_{i} containing C_{m_{i}}^{s} such that d_{C_{i}^{s}}(s) > d_{S}(s) + d_{X_{0}}(s); easily, such a C_{i}^{s} exists by (2) and the definition of S_{1}. It is now easy to check that (3) is indeed satisfied, and moreover for the case κ = ω we have in addition, for every Z and every s as in (3), that

d_{X}(s) > d_{S}(s) + d_{X_{0}}(s) for every X ∈ Z.  (4)

Now let U ⊆ V, and let π_{U} be any partition of U. We have to show that there is a partition χ of V extending π_{U} that is unfriendly for V \U.

For every β < κ, let G_{β} be the subgraph of G spanned by S and all components in X_{0} ∪ X_{β}. Note that r(G_{β}) ≤ r(G) for every β, and G_{β} − S has less components than G − S because |X_{0}| < κ and |X_{β}| < ω. Thus by our second induction hypothesis —or by our first induction hypothesis if r(G_{β}) < r(G)— there is a partition ρ_{β} of G_{β} that extends π_{U} ↾ (V (G_{β}) ∩ U) and is unfriendly for V (G_{β})\U.

Define the X_{0}-stamp of ρ_{β} to be the set of vertices s ∈ S_{0} that are given d(s) opponents within ⋃ X_{0} by ρ_{β}, i.e. those for which a_{ρ_{β}}(s, ⋃ X_{0}) = d(s) holds. Since S is finite, there is a partition ρ_{S} of S, a subset S′ of S_{0}, and a subsequence (ρ_{α})_{α∈J} of (ρ_{β})_{β<κ} with |J | = κ such that ρ_{α} ↾ S = ρ_{S} and the X_{0}-stamp of ρ_{α} is S′ for every α ∈ J. Using this subsequence, we will now construct a partition τ of G that is unfriendly for all but finitely many of the vertices in V \U, and later modify τ to obtain the desired partition χ that is unfriendly for V \U. For every α ∈ J, we partition X_{α} as in ρ_{α}; formally, for every vertex x in ⋃ X_{α}, let τ(x) := ρ_{α}(x). We proceed similarly with X_{0}: we pick some α_{0} ∈ J and then for every vertex x in ⋃ X_{0}, we let τ(x) := ρ_{α_{0}}(x). In order to partition the remaining vertices of the graph, we define the partition π_{U∪S} := π_{U} ∪ ρ_{S}; this is well-defined since ρ_{S} is by construction compatible with π_{U}. Now for every β ∈ κ\J we pick a partition ρ′_{β} of the graph G′_{β} := G[S ∪ V (⋃ X_{β})] that extends π_{U∪S} ↾ G′_{β} and is unfriendly for V (G′_{β})\(U ∪ S) — such a partition exists by our first inductive hypothesis, since r(G′_{β}) < r(G) — and again we partition the vertices in ⋃ X_{β} according to ρ′_{β}: for every vertex x in ⋃ X_{β}, we let τ(x) := ρ_{β}(x).

By construction, τ extends π_{U}. Moreover, it is straightforward to check that

τ is unfriendly for V \(S_{1} ∪ U).  (5)

Since the ρ_{α} have the same X_{0}-stamp for every α ∈ J, it follows that

for every s ∈ S_{0}, either a_{τ} (s, ⋃ X_{0}) = d(s) or for every α ∈ J there
holds a_{τ} (s, ⋃ X_{α}) = d(s) (or both).

(6)

Let F ⊆ S_{1} be the set of vertices of V \ U that are not happy in τ. We claim that

for every r ∈ F there holds d(r) = κ.  (7)

Indeed, pick any r ∈ S_{1} \ U with d(r) > κ. We need to show that this choice implies r ∉ F. By the definition of S_{0} and since r ∉ S_{0}, r cannot have full degree in ⋃ X_{0}, i.e. δ := d_{X_{0}}(d) < d(r). Define Z′ to be the set of those X_{α}, α ∈ J, for which d_{X_{α}}(r) ≤ δ. Since |Z′| ≤ |J | = κ < d(r) and δ < d(r), we obtain that d_{Z′}(r) ≤ κ · δ < d(r). Hence, from (3) it follows that |Z′| < κ and thus the set Z := {X_{α} : α ∈ J } \ Z′ has cardinality κ. Using (3) again yields d_{Z}(r) = d(r).

Now consider one such X_{α} ∈ Z. Recall that r is happy in the partition ρ_{α} of the graph G_{α}, which we defined to be the induced subgraph on S together with all components in X_{0} ∪ X_{α}. Since d_{X_{α}}(r) > δ = d_{X_{0}}(r), this means that r has, with respect to ρ_{α}, d_{X_{α}}(r) opponents in ⋃ X_{α}. Since τ and ρ_{α} coincide on ⋃ X_{α} by the definition of τ, this implies that a_{τ} (r, ⋃ X_{α}) = d_{X_{α}}(r). As, on the other hand, we have found that d_{Z}(r) = d(r), we deduce that r has d(r) opponents in τ and is therefore happy. Since F comprises unhappy vertices, we have proved (7).

We claim that F is empty if κ = ω. Indeed, if κ = ω then every vertex r in F has degree ω by (7) and so d_{X_{0}}(r) is finite. Thus by (4) and the fact that τ coincides with the partition ρ_{α} of G_{α}, which is unfriendly for V (G_{α})\U, τ gives r an opponent in X_{α} for every α ∈ J. But then r has |J | = κ = ω opponents in τ, contradicting the assumption that r ∈ F. Thus F = ∅ if κ = ω, which means that τ is unfriendly for V \ U and we are done. So we may from now on assume that

κ is an uncountable cardinal.  (8)

Denote by τ′ the partition obtained from τ by flipping F, i.e. by moving each vertex in F from its partition class in τ to the other partition class (formally, by changing the image under τ of every vertex in F). Then, τ′ is unfriendly for S\U, as all vertices in S have infinite degree by Lemma 2.2, but there might be vertices in the rest of the graph that were made unhappy by flipping F. It follows from (5) and (7) that the set Y of elements of C\X_{0} (we will turn our attention to X_{0} later) that contain vertices that are unhappy in τ′ has cardinality less than κ, because each vertex in F had less than κ opponents in τ.

We now modify τ′ within Y to obtain a new partition ϕ of G that is unfriendly for V \(V (⋃ X_{0}) ∪ U). For every component C ∈ Y, let U′ := (U ∩ V (C)) ∪ S, and pick a partition ϕ_{C} of G[S ∪ V (C)] that extends τ′ ↾ U′ and is unfriendly for V (C)\U′; such a partition exists by our first induction hypothesis as r(C) < r(G). Then, for every x ∈ V (C) put ϕ(x) := ϕ_{C}(x). Vertices that are not contained within Y we leave unchanged: for every x ∈ V \V (⋃ Y) put ϕ(x) := τ′(x).

We claim that

ϕ is unfriendly for V \(V (⋃ X_{0}) ∪ U).  (9)

Indeed, ϕ is by construction unfriendly for V \(V (⋃ X_{0}) ∪ U ∪ S). To see that it is unfriendly for S\U as well, recall that τ′ was unfriendly for S\U, and suppose there is an s ∈ S unhappy in ϕ. Since s was happy in τ′, it follows that s has d(s) many neighbours within Y, which puts s in S_{0} as |Y| < κ. But then by (6) if s is not given d(s) opponents in X_{0} by τ, and thus also by ϕ, then s is given d(s) opponents in each of the κ many X_{α} with α ∈ J that do not contain a component in Y, a contradiction. This establishes Claim (9).

Finally, we turn our attention to the unhappy vertices in ⋃ X_{0}. These vertices were happy in τ and thus had an opponent in τ that is lost in ϕ, which means that they are adjacent to a vertex in F. Observe that

γ := max{ω, max_{r∈F} a_{τ} (r, V (⋃ X_{0}))} < κ.  (10)

Indeed, recall that ω < κ by (8). Moreover, by the definition of S_{1} each vertex r ∈ F ⊆ S_{1} has less than full degree in V (⋃ X_{0}), and thus a_{τ} (r, V (⋃ X_{0})) ≤ d_{X_{0}}(r) < d_{G}(r). Since d_{G}(r) = κ by (7) the claim follows.

Let H := G[V (⋃ X_{0}) ∪ S] and define S′_{0} to be the set of vertices s ∈ S_{0} with a_{ϕ}(s, V (⋃ X_{0})) < d_{G}(s). Putting Ũ := (U ∩ V (H)) ∪ S′_{0} ∪ S_{1} we shall find a partition ρ of H with the following properties.

(i) ρ is unfriendly for V (H) \ Ũ;

(ii) ρ extends ϕ ↾ Ũ; and

(iii) for every x ∈ V (H) if d_{H}(x) > γ then ρ(x) = ϕ(x).

Intuitively, what ρ accomplishes is to repartition the vertices in X_{0} and part of the vertices in S_{0} in such a way that firstly, every vertex in X_{0} or S is made happy, and secondly, any vertex in S_{0} whose partition class we changed has relatively small degree. The latter condition on the degree will then help make sure that the happiness of the vertices in ⋃ X_{α} is not affected by the repartitioning imposed by ρ.

Before we construct ρ let us check that it would indeed allow us to finish the proof. For this, we modify ϕ within H according to ρ to obtain a new partition χ of G: for every x ∈ V (H) let χ(x) := ρ(x) and for every x ∈ V \V (H) let χ(x) := ϕ(x). The following table summarises the definitions of some of the partitions of G we have defined so far, and indicates which vertices are happy in each partition.

X_{0} C\X_{0} S_{0} F S_{1}\F
τ ✓  ✓  ✓ × ✓ composed from the ρ_{β}
τ′ ?  ?  ✓ ✓ ✓ obtained from τ by flipping F
ϕ ?  ✓  ✓ ✓ ✓ obtained from τ′ by changes in Y
χ ✓  ✓  ✓ ✓ ✓ obtained from ϕ by changes in H

We claim that χ is unfriendly for V \U. Indeed, any vertex x ∈ V (⋃ X_{0})\U is clearly happy by condition (i). For a vertex s ∈ S\U we distinguish three cases. If s ∈ S_{1} then s has less that d_{G}(s) neighbours in ⋃ X_{0} by the definition of S_{1}, and thus by (ii) s is happy in χ as it was happy in ϕ. If s ∈ S′_{0} then, by the definition of S′_{0} and (9), it had d_{G}(s) opponents outside ⋃ X_{0} in ϕ. As ϕ and χ coincide outside ⋃ X_{0} and as ϕ(s) = χ(s) by (ii), the vertex s is happy in χ. Finally, if s ∈ S_{0}\S′_{0} then χ(s) = ρ(s). As s is happy in ρ (within H) by (i) and as χ coincides with ρ on H, we find that s is happy in χ as well (note that d_{H}(s) = d_{G}(s) since s ∈ S_{0}). It remains to check that every vertex in V \(S ∪ V (⋃ X_{0}) ∪ U) is happy too. So consider a vertex x in ⋃ X_{α}\U for some ordinal α. Such an x was happy in ϕ, but since we changed the partition of S we may have made it unhappy in χ. This is however not the case: if s ∈ S and ϕ(s) ≠ χ(s), then by (ii) and (iii) we have s ∈ S_{0} and d_{G}(s) = d_{H}(s) ≤ γ < κ, where the last inequality is (10). Thus by (1) s has all its neighbours in ⋃ X_{0}, which means that s is not a neighbour of x. In conclusion, x is still happy in χ and this completes the proof that χ is unfriendly for V \U.

To finish the proof of the theorem we still need to construct the partition ρ. Define A to be the set of all vertices a in H\Ũ with d_{H}(a) ≤ γ. Denote by K the union of the vertex sets of all the components of H[A] that contain an unhappy vertex (with respect to ϕ). Observe that such an unhappy vertex must have been an opponent in τ of some vertex in F. Thus by (10) there are at most γ components of this kind, and as each of them has at most γ vertices we obtain

|K| ≤ γ.  (11)

By our second induction hypothesis the graph H is pre-partitionable, thus there is a partition ρ of H extending ϕ ↾ Ũ ∪ (V (H)\K) such that every vertex in K\Ũ is happy. Clearly, ρ satisfies (ii) and (iii).

To see that every vertex x in V (H)\(K ∪ Ũ) is happy too, which would complete the proof that (i) is satisfied as well, we note that ρ differs from ϕ only within K, and distinguish two cases. If d_{H}(x) ≤ γ, then since x ∉ K, its neighbourhood N_{H}(x) does not meet K by the definition of A, thus ϕ and ρ coincide in N_{H}(x). By the definition of K it follows that x was happy in ϕ, thus it is also happy in ρ as its neighbourhood was not repartitioned. If, on the other hand, d_{H}(x) > γ, then x was happy in ϕ because |F | is finite, γ is infinite, and x was happy in τ. But then x is happy in ρ by (11) since only vertices in K were repartitioned while changing ϕ to ρ.

4 More graphs with unfriendly partitions

In the rest of the paper we shall strengthen Theorem 1.1 by applying Theorem 2.3 to a larger finitely closed class than just F. A proof of Theorem 1.2 will follow as a corollary.

Given a graph G = (V, E), let V_{∞} be the set of all vertices of infinite degree, and denote by V^{∗} the set of those vertices in V_{∞} that have only finitely many neighbours in V_{∞}. Let W be the class of countable graphs G such that V^{∗}(G) is finite. In particular, W contains all countable graphs G for which V_{∞}(G) or V (G)\V_{∞}(G) is finite. Note that \overline{W} also contains all uncountable graphs G for which V_{∞}(G) is finite, since deleting V_{∞}(G) shows that G has rank 1 in \overline{W}. Clearly, W is finitely closed. We claim that

Theorem 4.1. Every graph in \overline{W} is pre-partitionable. In particular, every such graph has an unfriendly partition.

In order to prove this we will need the following lemma from [1, Lemma 3].

Lemma 4.2. Let G = (V, E) be a countable graph and let U be a subset of V such that only finitely many vertices in V \U have infinite degree (in G). Then for every partition π of G[U] there exists a partition π′ of G that extends π and which is unfriendly for V \U.

Proof of Theorem 4.1. Consider a graph G in W. We will prove that G has an unfriendly partition. It is easy to modify this proof in order to show that G is pre-partitionable. The theorem then follows from Theorem 2.3.

First, let us construct an unfriendly partition π of G[V_{∞}\V^{∗}]. Observe that |V^{∗}| < ∞ implies that every vertex in G[V_{∞}\V^{∗}] has infinite degree. Pick a sequence (v_{i})_{i∈ℕ} in which every vertex in V_{∞}\V^{∗} appears infinitely often. We go through this sequence, and if π(v_{i}) has not been defined yet we set π(v_{i}) = 0. Otherwise, we choose a neighbour y ∈ V_{∞}\V^{∗} of v_{i} with π(y) still undefined and set π(y) := 1 − π(v_{i}). It is now easy to check that π is indeed unfriendly.

Next, Lemma 4.2 yields a partition π′ of G extending π so that π is unfriendly for V (G)\(V_{∞}\V^{∗}). Since every vertex in V_{∞}\V^{∗} already had infinitely many opponents in π, it follows that π′ is unfriendly for all of V (G).

The countable graphs in \overline{W} can be characterised as follows.

Proposition 4.3. A countable graph G lies in \overline{W} if and only if it contains no comb with all teeth in V^{∗}(G).

Proof. Suppose there are graphs in \overline{W} that contain a comb with all teeth in V^{∗}(G). Then, there is such a graph G that has minimal rank among all those graphs; let C be a comb in G with all its teeth in V^{∗}(G). Clearly, G does not have rank 0, so there is a finite set S of vertices such that all components of G − S have rank smaller than r(G). But one of the components contains a tail of C, contradicting the minimality of r(G).

Conversely, let G be a countable graph not in \overline{W}. Then there is a component C_{0} of G that does not lie in \overline{W} (otherwise S = ∅ is a separator as in Definition 2.1 showing that G ∈ \overline{W}). Since C_{0} ∉ W although C_{0} is countable, there is a vertex v_{0} ∈ V^{∗} in C_{0}. At least one component C_{1} of C_{0} − v_{0} is not in \overline{W}, and thus contains a vertex v_{1} ∈ V^{∗}(G). Let P_{1} be a v_{0}–v_{1} path in C_{1} ∪ {v_{0}}. Now recursively for i = 1, 2, …, let C_{i} be a component of C_{i−1} − P_{i−1} that is not in \overline{W}, let v_{i} be a vertex of V^{∗} in C_{i} and let P_{i} be a V (P_{i−1} ∩ C_{i−1})–v_{i} path in G[C_{i} ∪ P_{i−1}]. It is not hard to see that ⋃_{i<ω} P_{i} is a comb with teeth v_{0}, v_{1}, … in V^{∗}.

As remarked earlier, the class U of (countable or uncountable) graphs that have only finitely many vertices of infinite degree is contained in \overline{W}. And as in the proof of Proposition 4.3 we see that any graph not in \overline{U} contains a comb whose leaves all have infinite degree; let us call such a comb a brush. Graphs not containing a brush thus lie in \overline{U} ⊆ \overline{\overline{W}} = \overline{W}, and we obtain Theorem 1.2 as a corollary of Theorem 4.1:

Corollary 4.4. Every graph not containing a brush has an unfriendly partition.

Acknowledgement

We would like to thank Matt DeVos for inspiring discussions on this subject.

References

[1] R. Aharoni, E.C. Milner, and K. Prikry. Unfriendly Partitions of a Graph. J. Combin. Theory (Series B), 50:1–10, 1990.

[2] R. Diestel. Graph Theory (3rd edition). Springer-Verlag, 2005.

Electronic edition available at:

   http://diestel-graph-theory.com/index.html.

[3] R. Schmidt. Ein Ordnungsbegriff für Graphen ohne unendliche Wege mit einer Anwendung auf n-fach zusammenhängende Graphen. Arch. Math., 40:283–288, 1983.

[4] S. Shelah and E.C. Milner. Graphs with no unfriendly partitions. In: A tribute to Paul Erdős, pages 373–384. Cambrigde Univ. Press, 1990.