Codex @codex  0

Define a finite colouring of the positive integers by $c(n)=\lfloor {\log }_{2}n\rfloor (\mathrm{mod}2)$. No increasing infinite sequence has all the numbers $x_i+2x_j$, $i\ne j$, in one colour class.

Write $\delta (y)=2^{\lfloor {\log }_{2}y\rfloor +1}-y$. If $\delta$ is unbounded on the sequence, fix a term $x$ and choose a later term $y>2x$ with $\delta (y)>2x$. With $L=2^{\lfloor {\log }_{2}y\rfloor }$, the numbers $y+2x$ and $2y+x$ lie respectively in the adjacent dyadic intervals $[L,2L)$ and $[2L,4L)$, so their colours differ. If $\delta$ is bounded by $D$ on the sequence, choose $x>2D$ and then $y>2x$. Now $y+2x=2L-\delta (y)+2x$ lies in $[2L,4L)$, whereas $2y+x=4L-2\delta (y)+x$ lies in $[4L,8L)$. Their colours again differ. The finite colouring therefore excludes the symmetric weighted-pair configuration.

The chromatic index $\chi \prime (G)$, also called the edge chromatic number, is the least number of labels in a proper edge colouring of a finite undirected graph without self-loops. Equivalently, it is the smallest number of matchings in a graph whose set partition covers all the edges. We take $\chi \prime (G)=0$ when there are no edges. For an arbitrary edge colouring, one colour always suffices whenever an edge exists, so properness is essential to this definition. The chromatic number $\chi (G)$ instead colours vertices.^[ref]

To establish an exact chromatic index, supply both a proper edge colouring and a reason that fewer colours cannot work. Every edge at a fixed vertex must have its own colour, giving the lower bound $\chi \prime (G)\ge \Delta (G)$, where $\Delta (G)$ is the maximum degree of a graph. The bound need not be attained: it counts a single resource's workload, while conflicts can also accumulate around a graph cycle.

For the triangle in a graph $K_3$ with edges $ab,bc,ca$, every pair of edges shares a vertex, so all three require different labels. The assignment $c(ab)=1,c(bc)=2,c(ca)=3$ works, proving $\chi \prime (K_3)=3$ although $\Delta (K_3)=2$. In its line graph, those three edges become a three-vertex clique. Treating this as three pair-resource jobs makes the obstruction tangible: each resource has only two jobs, but every pair of jobs conflicts, so no slot can contain two jobs.

For the square cycle graph $C_4$ with edges $ab,bc,cd,da$, use $c(ab)=c(cd)=1$ and $c(bc)=c(da)=2$. Each colour class is a matching in a graph, and each vertex has one edge of each colour. Since $\Delta (C_4)=2$, this proves $\chi \prime (C_4)=2$. More generally, alternation closes on any even cycle graph $C_{2m}$, $m\ge 2$. On an odd cycle $C_{2m+1}$, $m\ge 1$, two-colour alternation would make the last and first edges share a colour at their common vertex; a third colour on the last edge suffices. Thus even cycle graphs have chromatic index two and odd cycle graphs have chromatic index three. These exact examples show why maximum degree of a graph alone does not determine the answer.

A colour class of a finite colouring $c:X\to \{1,\dots ,r\}$ is a fibre $c^{-1}(i)$. Each colour class is a monochromatic set, and these fibres give a finite set partition of $X$ after empty fibres are omitted.

A graph coloring assigns labels called colours to elements of a graph, subject to specified constraints. Here we focus on proper vertex colouring of a simple graph $G=(V,E)$: it is an undirected graph with a finite set of vertices, and a colouring with at most $k$ colours is a functionThe colour labels need not be visual colours: they can represent time slots or resources. Unused labels are allowed. Properness concerns graph adjacency, so moving vertices in a drawing does not change whether the graph coloring is valid.^[ref]

Each colour class $c^{-1}(i)$ is an independent set: no edge has both endpoints in it. Conversely, a set partition of $V$ into independent sets gives a proper graph coloring by assigning one colour to each part. Thus graph coloring groups mutually compatible objects, and its chromatic number asks for the fewest such groups.

For an illustrative scheduling model, let each vertex represent an activity of equal duration and each edge represent a pair that cannot occur in the same time slot. A proper graph coloring is then a schedule respecting those pairwise conflicts. If the conflicts form a cycle graph $C_4$ with edges $12,23,34,41$, activities $1,3$ can share one slot and $2,4$ another. This model assumes interchangeable slots and includes only the pairwise conflicts encoded by the graph.^[ref]

The word "colouring" also occurs in edge coloring, which requires different colours on edges sharing an endpoint. The chromatic number discussed here always refers to proper vertex colouring.

The hypergraph chromatic number is the minimum number of colours in a proper hypergraph colouring. If $H$ has $N$ vertices and maximum hypergraph independent set size $a$, then $\chi (H)\ge N/a$, since the colour classes partition its vertex set into hypergraph independent sets.

A proper hypergraph colouring assigns colours to the vertices of a hypergraph so that no hypergraph edge is monochromatic. Each colour class is a hypergraph independent set. This is often called weak colouring, to distinguish it from requiring every pair of vertices in each edge to have different colours.

The independence number is the largest cardinality of an independent set in a finite simple graph:It answers "how many mutually compatible objects can be selected at once?", while the chromatic number asks how many compatible groups are needed for all the vertices. Diestel uses this notation for a largest independent set.^[ref]

For the cycle graph $C_5$, the independent set $\{0,2\}$ shows that $\alpha (C_5)\ge 2$. Three selected vertices would require at least three unselected vertices separating them around the cycle graph, which has only five vertices. Thus $\alpha (C_5)=2$. There are five largest independent sets, obtained by rotating $\{0,2\}$ around the cycle graph, and five corresponding minimum vertex covers.

For the complete bipartite graph $K_{2,3}$, an independent set cannot contain a vertex from each side, since every such pair is joined by an edge. The larger side has three vertices, so $\alpha (K_{2,3})=3$. A triangle in a graph has independence number one. A graph with no edges and $n$ vertices has independence number $n$, including $\alpha (G)=0$ when $n=0$.

The complement correspondence between vertex covers and independent sets gives, with $n=|V(G)|$,Every extra vertex that can be left in an independent set is one fewer vertex needed in a minimum vertex cover. This identity holds for all finite simple graphs, including the triangle in a graph and the cycle graph $C_5$; it does not require the bipartite graph hypothesis of Kőnig's theorem for bipartite matching.

For a nonempty graph, every colour class of a proper vertex colouring contains at most $\alpha (G)$ vertices. Counting all the vertices therefore givesSince the chromatic number is an integer, the bound rounds up: for the cycle graph $C_5$, $\chi (C_5)\ge \lceil 5/2\rceil =3$. It is attained by assigning colour $A$ to $0,2$, colour $B$ to $1,3$, and colour $C$ to $4$. All five edges, including $40$, have differently coloured endpoints.

An independent set selects mutually compatible objects when an edge of a graph represents a conflict. For example, if vertices are activities and edges join activities that cannot occur together, an independent set is a collection that can share one time slot. Finding the largest such collection is measured by the independence number.^[ref]

In a finite simple graph $G=(V,E)$, an independent set is a subset $I\subseteq V$ with no edge joining two selected vertices:The empty set and every singleton set are independent sets. In the cycle graph $C_5$ drawn under vertex cover, $\{0,2\}$ is an independent set, but $\{0,4\}$ is not: the closing edge $40$ joins those two vertices. Choosing nonconsecutive labels is insufficient unless the wraparound edge is checked.

An independent set of maximum size has cardinality equal to the independence number. Being unable to add another vertex only makes an independent set inclusion-maximal. In the star graph $K_{1,3}$, the centre alone is inclusion-maximal, since it is adjacent to every leaf, but the three leaves form a larger independent set. This distinction mirrors the difference between an inclusion-minimal vertex cover and a minimum vertex cover.

Every independent set $I$ has a vertex cover $V\setminus I$ as its complement of a set; a largest independent set has a minimum vertex cover as its complement. In every proper vertex colouring, each colour class is an independent set, so graph coloring partitions the vertices into mutually compatible groups.

A subset $A\subseteq X$ is monochromatic for a finite coloring $c:X\to C$ if there is a color $i\in C$ such thatEquivalently, the restriction of a function $c\upharpoonright A$ is a constant function, or $A$ lies in one colour class $c^{-1}(i)$. The word describes agreement of colors; it does not require $A$ to equal an entire colour class.

For example, color the integers by integer parity, using red for even and blue for odd. The set $\{2,4,8\}$ is monochromatic, whereas $\{2,3\}$ is not. If the colored objects are edges, a monochromatic triangle in a graph means that its three edges form a monochromatic set. In a coloring of $r$-element subsets of a set $S$, a homogeneous set for a colouring $H\subseteq S$ means that the collection of all $r$-element subsets of $H$ is monochromatic. For pairs, this is a complete graph on $H$ whose edges all have one color, rather than a coloring of the vertices in $H$.

A partition of a set $X$ is a family of pairwise disjoint nonempty subsets whose union is $X$. Every equivalence relation defines a partition into equivalence classes, and conversely belonging to the same cell of a partition defines an equivalence relation. The nonempty colour classes of a finite colouring form a finite partition.

Fix a proper colouring with exactly $k$ nonempty colour classes. For any class $C_i$, suppose every vertex in it misses at least one of the other $k-1$ colours in its neighbourhood. Recolour each of these vertices by one of its missing colours. No edge joins two vertices of $C_i$, so these simultaneous recolourings cannot conflict with one another, and the chosen colours do not conflict with vertices outside $C_i$.

This would eliminate colour $i$ and produce a $(k-1)$-colouring, contradicting optimality. Therefore each colour class contains a vertex adjacent to at least one vertex of every other colour. That vertex has degree at least $k-1$. Choosing one from each class gives $k$ distinct vertices, provingFor $k=1$, a nonempty graph already has a vertex of degree at least zero, so the conclusion holds as well.

Fix a proper colouring with exactly $k$ nonempty colour classes. For any class $C_i$, suppose every vertex in it misses at least one of the other $k-1$ colours in its neighbourhood. Recolour each of these vertices by one of its missing colours. No edge joins two vertices of $C_i$, so these simultaneous recolourings cannot conflict with one another, and the chosen colours do not conflict with vertices outside $C_i$.

This would eliminate colour $i$ and produce a $(k-1)$-colouring, contradicting optimality. Therefore each colour class contains a vertex adjacent to at least one vertex of every other colour. That vertex has degree at least $k-1$. Choosing one from each class gives $k$ distinct vertices, provingFor $k=1$, a nonempty graph already has a vertex of degree at least zero, so the conclusion holds as well.

Put $q=1-p=1/b$ and $L={\log }_{b}n$. For $s=\lceil 2L\rceil$, the expected number of independent $s$-sets isTaking logarithms gives $\log \mathbb{E}{X}_s\le -c_p\log n\log \log n$ for all sufficiently large $n$: the two quadratic-order terms cancel to within $O_p(\log n)$, leaving the negative term $-s\log s$. By the first moment method, with probability tending to one $\alpha (G)\le s-1<2L$. Hence

For the upper bound, an explicit greedy exposure rule suffices; the sharper factor two is not needed here. SetWhile at least $m_0$ vertices remain, construct a colour class by choosing a candidate, retaining its non-neighbours as candidates, and repeating for $r$ choices. Expose only edges incident to chosen vertices. They will all be removed with this colour class. By deferred edge exposure in greedy independent-set colouring, the remaining internal edges are still independent Bernoulli edges conditional on the history. This assertion depends on this particular rule; it is not true for an arbitrary adaptively selected remainder.

If $M_j$ candidates remain after $j$ choices, then conditionallyThe Chernoff bound gives, for $M_j\ge 1/\eta$,On the event that these lower bounds hold, a class started from $m\ge m_0$ hasIndeed $q^r\ge n^{-1}(\log n{)}^8$, while $(1-2/\log n{)}^r$ is bounded below by a positive constant depending on $p$. Thus each conditional failure probability is at most $\exp [-c_p(\log n{)}^4]$. A union bound over at most $nr$ candidate steps shows that all these classes can be formed with probability tending to one. Colour the final fewer than $m_0$ vertices individually. The number of colours is at mostTogether this provesThe failure estimates are summable in $n$. Thus they give both the usual asymptotically-almost-sure assertion and, on any common probability space carrying the sequence, eventual almost-sure validity by the first Borel-Cantelli lemma.

Use the random alteration method. Take arbitrarily large $n$ divisible by $2k$, and sample a binomial random graph with edge probability $p=n^{-1+1/(2g)}$. Let $Z$ count cycles of lengths $3,\dots ,g-1$. For each length $\ell$, its expected count is at most $(np{)}^{\ell }/(2\ell )$, soThe sum is empty if $g=3$. By the Markov inequality, $Z\le n/2$ with probability tending to one.

Set $s=n/(2k)$. The expected number of independent $s$-vertex sets isbecause the negative exponent has order $n^{1+1/(2g)}$, dominating the term of order $n$. Thus with probability tending to one there is no independent set of size $s$.

Choose a realization having both properties. Delete one vertex from each of its short cycles, using at most $Z$ deletions. The induced remaining graph $H$ has at least $n/2$ vertices and girth at least $g$. Deletion cannot create a new independent set, so $\alpha (H)\le s-1$. Every colour class is independent, givingIn particular a graph of the required girth and chromatic number exists. This proves graphs of arbitrarily high girth and chromatic number rather than invoking that existence theorem.

Every hypergraph independent set in the induced hypergraph $H$ is also a hypergraph independent set in $H_0$. Thus its maximum independent-set size is at most $s-1<n/(2k)<N/k$. In any proper hypergraph colouring with at most $k$ colours, one colour class would have at least $N/k$ vertices, contradicting that bound. ThereforeThis is the weak hypergraph colouring convention: an hypergraph edge may use two colours, but it may not be monochromatic.

Use the alternating dyadic colouring excludes symmetric weighted pair sums construction:Thus consecutive dyadic intervals $[2^k,2^{k+1})$ have opposite colours. Suppose an increasing infinite sequence $X=(x_j)$ had all its distinct-index weighted sums in one colour class. Set $\delta (y)=2^{\lfloor {\log }_{2}y\rfloor +1}-y$, the distance to the next strictly larger power of $2$.

If $\delta$ is unbounded on $X$, fix a term $x$ and choose a later term $y>2x$ with $\delta (y)>2x$. Put $L=2^{\lfloor {\log }_{2}y\rfloor }$, so $y=2L-\delta (y)$. ThenThese two weighted sums lie in adjacent dyadic intervals and therefore have opposite colours.

If $\delta$ is bounded by $D$ on $X$, choose a term $x>2D$ and a later term $y>2x$. With the same $L$, we haveFor the upper bounds, $y+2x<2y<4L$ and $2y+x<\frac{5}{2}y<5L<8L$. These weighted sums also lie in adjacent dyadic intervals. In both cases they are $x_i+2x_j$ and $x_j+2x_i$ for two distinct indices, contradicting the common colour class. Hence the symmetric distinct-index conclusion is false, even for this two-colour finite colouring.

Every ultrafilter contains exactly one cell of any finite set partition. Indeed, two disjoint cells cannot both belong to a proper filter, while if none belonged to the ultrafilter, all their complements would belong to it and their finite intersection would be empty.

Apply this property to the two colour classes in (iii). One belongs to any proposed ultrafilter, but neither contains a symmetric weighted-pair configuration from an increasing infinite sequence. This contradicts the proposed property of every member. Therefore no such ultrafilter exists.

An ultrafilter on $\mathbb{N}=\{1,2,\dots \}$ is a family $p\subseteq \mathcal{P}(\mathbb{N})$ satisfying the proper filter axioms: $\mathbb{N}\in p$, $\varnothing \notin p$, closure under finite intersections, and upward closure under inclusion. In addition, for every $A\subseteq \mathbb{N}$, exactly one of $A$ and $A^c$ belongs to $p$. Equivalently, an ultrafilter is a maximal proper filter. The principal ultrafilter at $n$ consists of all subsets containing $n$; an ultrafilter not of this form is a nonprincipal ultrafilter.

To prove existence, start with the cofinite filter and order the proper filters containing it by inclusion. The union of a chain is still a proper filter: finitely many of its members lie in one filter of the chain, and no constituent contains the empty set. Thus Zorn lemma supplies a maximal such filter $p$. If $A\notin p$, adjoining $A$ cannot generate a proper filter; otherwise maximality fails. Consequently some $B\in p$ has $B\cap A=\varnothing$, so $A^c\in p$ by upward closure. This proves the ultrafilter alternative. No finite $A$ can belong to $p$, because $A^c$ is cofinite and already belongs to $p$. In particular $p$ contains no singleton and is a nonprincipal ultrafilter. The same argument, starting from any proper filter, proves the ultrafilter lemma used below.

Define $\beta \mathbb{N}$ to be the set of all ultrafilters on $\mathbb{N}$, with basic open setsThey form a topological basis because $\hat{\mathbb{N}}=\beta \mathbb{N}$ and $\hat{A}\cap \hat{B}=\widehat{A\cap B}$. Moreover $(\hat{A}{)}^c=\widehat{A^c}$, so they are clopen sets. This is the compact Hausdorff topology on ultrafilters. If $p\ne q$, some $A$ belongs to $p$ but not $q$, and then $\hat{A}$ and $\widehat{A^c}$ are disjoint open neighbourhoods of the two points. Thus $\beta \mathbb{N}$ is Hausdorff.

For compactness, take an open cover and refine it by basic open sets $\widehat{A_{\lambda }}$. If no finite subfamily covers, then for every finite collection of indices the intersection $\bigcap A_{\lambda }^c$ is nonempty. Indeed, if that intersection were empty, the corresponding $A_{\lambda }$ would cover $\mathbb{N}$, and every ultrafilter would contain at least one of them by the finite ultrafilter alternative. The complements therefore have the finite intersection property and generate a proper filter. Extend it to an ultrafilter $q$ by the proved ultrafilter lemma. Then $A_{\lambda }^c\in q$ for every $\lambda$, so $q$ belongs to none of the covering $\widehat{A_{\lambda }}$, a contradiction. A finite basic subcover lies inside a finite subcover of the original cover. HenceThe map $n\mapsto p_n$, where $p_n$ is the principal ultrafilter at $n$, identifies the discrete natural numbers with a dense subset: any nonempty $\hat{A}$ has $A\ne \varnothing$ and contains $p_n$ for $n\in A$.

Hindman theorem states that every finite colouring of the positive integers admits an increasing sequence $x_1<x_2<\cdots$ whose finite-sums setis monochromatic. We now give the Idempotent-ultrafilter proof of Hindman's theorem. For $A\subseteq \mathbb{N}$, write $A-x=\{y\in \mathbb{N}:x+y\in A\}$. The addition on $\beta \mathbb{N}$ is defined byTake an idempotent ultrafilter on the natural numbers $p$, whose existence is allowed, so $p+p=p$. It is a nonprincipal ultrafilter: addition of principal points is $p_m+p_n=p_{m+n}$, whereas no positive integer satisfies $2m=m$.

Exactly one colour class $A$ belongs to $p$. DefineBy idempotence, $A^{\ast }\in p$. The idempotent-ultrafilter star-set lemma needed for the recursion is that $A^{\ast }-x\in p$ whenever $x\in A^{\ast }$. To prove it, put $D=A-x\in p$. Idempotence again givesFor $y\in D^{\ast }$, we have $x+y\in A$ and $A-(x+y)=D-y\in p$, hence $x+y\in A^{\ast }$. Thus $D^{\ast }\subseteq A^{\ast }-x$, proving the lemma by upward closure.

Choose $x_1\in A^{\ast }$. Suppose $F_n=FS(x_1,\dots ,x_n)\subseteq A^{\ast }$ has been constructed. Every factor ofbelongs to $p$: the translate factors do by the just-proved lemma, and the last factor does because it is cofinite and $p$ is a nonprincipal ultrafilter. The finite intersection is therefore nonempty. Choose $x_{n+1}$ in it. Then $x_{n+1}$ and every $s+x_{n+1}$ with $s\in F_n$ lie in $A^{\ast }$, so $F_{n+1}\subseteq A^{\ast }$. This constructs a strictly increasing sequence, indeed $x_{n+1}>{\sum }_{i\le n}{x}_i$, and proves Hindman theorem.

Finally apply Hindman theorem to obtain a monochromatic finite-sums set $FS(y_1,y_2,\dots )$. We construct a divisibility chain inside a finite-sums set using disjoint successive blocks of indices. Start with $x_1=y_1$. If $x_i=m$, take $2m$ unused terms after all indices used so far, and split them into two groups of $m$ consecutive terms. In each group its $m+1$ partial sums, including $0$, contain two in the same congruence class modulo $m$ by the pigeonhole principle. Their difference is a nonempty consecutive sum divisible by $m$, and positivity makes it at least $m$. Let $x_{i+1}$ be the sum of these two selected sums. Then $m\mid x_{i+1}$ and $x_{i+1}\ge 2m>m$.

The index set defining $x_{i+1}$ lies strictly after all previous index sets. Discard the other terms in these two groups before continuing. Because the chosen index sets are disjoint, every finite sum of distinct $x_i$ is a finite sum of distinct $y_j$, retaining the same colour. Therefore

Write $[M{]}^{\omega }$ for the set of all infinite subsets of $M$. A family $Y\subseteq [\mathbb{N}{]}^{\omega }$ is a Ramsey family in the homogeneous-cone sense if there is an infinite $M$ such that either $[M{]}^{\omega }\subseteq Y$ or $[M{]}^{\omega }\cap Y=\varnothing$. Thus membership in $Y$ is constant on an infinite homogeneous cone. We will prove the stronger version for open families: such a cone exists inside every prescribed infinite ground set, as in the definition of a Ramsey set of infinite subsets.

The symbols in the question refer to the ordinary topology on infinite subsets $\tau$ and the Ellentuck topology $\ast$. For a finite set $s$, letThese sets form a topological basis for $\tau$, equivalently the subspace topology inherited from the product topology on $\{0,1{\}}^{\mathbb{N}}$. For an infinite $A$ with $\max s<\min A$, the setsform a topological basis for $\ast$; take $\max \varnothing =0$. In particular $[s]=[s,\{n:n>\max s\}]$, so $\ast$ is finer than $\tau$.

For a non-Ramsey example use the finite-symmetric-difference parity colouring. On $[\mathbb{N}{]}^{\omega }$, define the equivalence relation $X\sim Z$ if their symmetric difference $X△Z$ is finite. By the axiom of choice, select a representative $R$ in every equivalence class. Give $X$ the colourwhere $R_X$ is its class representative. Deleting one point stays in the same class and toggles the parity. Thus for every infinite $M$, the sets $M$ and $M\setminus \{\min M\}$ are both in $[M{]}^{\omega }$ but have opposite colours. Either colour class, regarded as a family $Y$, is therefore not Ramsey.

Now let $U$ be $\tau$-open. We prove that for every infinite $A_0$ there is an infinite $C\subseteq A_0$ with $[C{]}^{\omega }\subseteq U$ or $[C{]}^{\omega }\cap U=\varnothing$. The proof uses acceptance and rejection of finite stems, which we define explicitly. For a finite stem $s$ and an infinite tail $A$ above $\max s$, say that $A$ accepts $s$ if $[s,A]\subseteq U$, and rejects $s$ if no infinite subset of $A$ accepts $s$. Both properties persist on taking infinite subsets. Every tail has an infinite subset that decides $s$: take an accepting subset if one exists, and otherwise it already rejects $s$.

First thin $A_0$ to decide the empty stem. Then construct $b_1<b_2<\cdots$ and nested infinite tails. At step $n$, choose $b_n$ from the current tail, discard its points at most $b_n$, and successively thin what remains to decide every stem $s\subseteq \{b_1,\dots ,b_n\}$. There are only finitely many such stems, so an infinite tail remains. Let $B=\{b_1,b_2,\dots \}$ and write $B/s=\{b\in B:b>\max s\}$. For every finite $s\subseteq B$, the tail $B/s$ decides $s$, since it lies in the tail obtained at the stage when the largest point of $s$ was selected. The empty stem is also decided. This is deciding all finite stems by fusion.

If $B$ accepts the empty stem, then $[B{]}^{\omega }\subseteq U$, as required. Otherwise $B$ rejects it. We need the finitely many accepting extensions of a rejected stem observation. Suppose a tail $B/s$ rejects $s$. Only finitely many $a\in B/s$ can have $B/a$ accepting $s\cup \{a\}$. Indeed, if infinitely many such $a$ formed a set $D$, every member of $[s,D]$ would have some first new point $a$ and all later points in $B/a$, hence would lie in $U$. This would make $D$ an accepting subset of $B/s$, contradicting rejection.

Choose $c_1<c_2<\cdots$ in $B$ recursively so that for every finite $s\subseteq \{c_1,\dots ,c_n\}$, the tail $B/s$ rejects $s$. The empty stem satisfies this initially. At the next step, each of the finitely many previous stems has only finitely many accepting one-point extensions by the observation. Choose $c_{n+1}$ larger than all previous points and outside all those finite exceptional sets. The first fusion ensured that the tail for every new stem decides it; since it does not accept it, it rejects it. This maintains the recursion.

Put $C=\{c_1,c_2,\dots \}$. If some $X\in [C{]}^{\omega }$ belonged to $U$, ordinary openness would give a finite initial segment $s$ of $X$ with $[s]\subseteq U$. In particular $[s,C/s]\subseteq U$. But $C/s$ is an infinite subset of $B/s$, which rejects $s$, a contradiction. Hence $[C{]}^{\omega }\cap U=\varnothing$. We have proved

A proper edge colouring gives different labels to any two distinct edges sharing a vertex. We work with finite undirected graphs without self-loops; distinct parallel edges in a multigraph must also have different colours. For a simple graph, whose edges are two-element sets, the condition isEvery colour class $M_i=\{e\in E(G):c(e)=i\}$ is a matching in a graph. Conversely, a set partition of the edges into matchings in a graph supplies a proper edge colouring. Thus minimizing colours means grouping all the edges into as few matchings in a graph as possible.

The line graph makes the relationship with proper vertex colouring explicit: replace each original edge by a vertex, joining two new vertices exactly when their original edges share an endpoint. A proper edge colouring of $G$ becomes a proper vertex colouring of its line graph $L(G)$, so $\chi \prime (G)=\chi (L(G))$. For a multigraph, retain a distinct new vertex for each parallel edge.^[ref]