I got stuck on the following problem while thinking about [this question](https://mathoverflow.net/questions/305003/does-vizings-conjecture-hold-for-the-infinite-graphs).


Let $G$ be an infinite graph. Say that a set of vertices $S$ of $G$ *has a dominating pair* if there exist $v,w \in S$ such that every other vertex in $S$ is adjacent to either $v$ or $w$ (or both).


Suppose there is a finite set of vertices $S\_0$ every finite superset of which has a dominating pair. Does the whole graph have a dominating pair?



Domination numbers of infinite graphs
I think I have a counterexample. I will construct the *complement* of the graph $G$ as the union of an infinite sequence of finite graphs $H\_n.$


Let $H\_0$ be a graph with three vertices and no edges.


Suppose the finite graph $H\_n$ has been constructed with vertex set $V\_n=V(H\_n).$ Then $H\_{n+1}$ is a supergraph of $H\_n$ consting of the vertices and edges of $H\_n$ and the following new vertices and edges: For each unordered pair $\{u,v\}\in\binom{V\_n}2$ such that $u,v$ have no common neighbor in $H\_n,$ create a new vertex $w\_{\{u,v\}}$ and edges joining $w\_{\{u,v\}}$ to $u$ and $v.$ Let me define $u\*v=v\*u=w\_{\{u,v\}}.$


Let $H=\bigcup\_{n=0}^\infty H\_n$ and let $G=\overline H$ be the complement of $H.$


Plainly, $G$ has no dominating pair, since every pair of vertices in $H$ has a common neighbor.


It is important that $G$ and $H$ are *infinite* graphs, i.e., the sequence $H\_0,H\_1,H\_2,\dots$ does not stop growing. Maybe this is obvious. It wasn't obvious to me, but anyway it follows from this lemma:


**Lemma.** If $H\_n$ contains three independent vertices, no two of which have a common neighbor, then so does $H\_{n+2}.$


**Proof.** Suppose $a,b,c\in V\_n$ are three distinct vertices, no two of them connected by a path of length $\le2$ in $H\_n.$ Then in $H\_{n+1}$ we have a vertex $a\*b$ joined to $a$ and $b,$ a vertex $a\*c$ joined to $a$ and $c,$ and a vertex $b\*c$ joined to $b$ and $c;$ and these new vertices have no other neighbors in $H\_{n+1}.$ Then $a$ and $b\*c$ have no common neighbor in $H\_{n+1},$ nor do $b$ and $a\*c,$ nor do $c$ and $a\*b.$ Finally, in $H\_{n+2},$ the three vertices $a\*(b\*c),b\*(a\*c),c\*(a\*b)$ are independent and have no common neighbors.


Let $V=\bigcup\_{n=0}^\infty V\_n=V(G)=V(H).$ I claim that every *proper* subset of $V$ which contains the finite set $V\_0$ has a dominating pair in $G$. 


It will suffice to show that, if $S$ has no dominating pair in $G$, and if $V\_n\subseteq S,$ then $V\_{n+1}\subseteq S.$ Recall that any element of $V\_{n+1}\setminus V\_n$ is of the form $u\*v$ for some $u,v\in V\_n.$ By the construction, $u\*v$ is the *only* common neighbor of $u$ and $v$ in $H,$ whence $\{u,v\}$ would be a dominating pair in $G$ for any set of vertices which contained $u$ and $v$ but not $u\*v.$


