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?

  • $\begingroup$ This sounds like a job for the compactness theorem. Gerhard "Turn On The Omega Signal!" Paseman, 2018.07.15. $\endgroup$ Jul 16, 2018 at 2:50
  • $\begingroup$ @GerhardPaseman: how? Maybe the dominating pairs of the finite supersets fly off to infinity... $\endgroup$
    – Nik Weaver
    Jul 16, 2018 at 2:56
  • 1
    $\begingroup$ I don't know how. Perhaps they do fly, but all the vertices in the finite set are adjacent to one or the other of them. It makes me think that if no given pair dominates, then there is a finite subset containing that pair that has no dominating pair. Unfortunately I do not have an answer for this. Gerhard "That's Why It's A Comment" Paseman, 2018.07.15. $\endgroup$ Jul 16, 2018 at 3:26
  • $\begingroup$ +1 for "That's Why It's A Comment" $\endgroup$
    – Nik Weaver
    Jul 16, 2018 at 13:37

1 Answer 1


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.$

  • $\begingroup$ Yeah, this works. Nice! $\endgroup$
    – Nik Weaver
    Jul 17, 2018 at 16:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .