Domination numbers of infinite graphs I got stuck on the following problem while thinking about this question.
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?
 A: 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.$
