For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x, y\in X\text{ and } x\neq y\big\}$.

Let $G=(V,E)$ be a simple, undirected graph, and suppose ${\cal V}$ is a collection of subsets of $V$ such that for all $W, W' \in {\cal V}$ we have either $W\subseteq W'$ or $W' \subseteq W$.

If for all $W\in {\cal V}$ the induced subgraph $(W,E\cap [W]^2)$ is vertex-transitive, is the induced subgraph $(\bigcup {\cal V}, E\cap [\bigcup{\cal V}]^2)$ necessarily vertex-transitive as well?

(Applying Zorn's Lemma, which is equivalent to the Axiom of Choice, a positive answer would imply that every graph has a maximal vertex-transitive subgraph.)


Let $Q$ be a chain (totally ordered set). Let $Y_Q$ be the graph whose set of vertices is the set of pairs $(x,y)$ with $x,y\in Q$ and $x<y$, and an edge between $(x,y)$ and $(x',y')$ iff the intervals $]x,y[$ and $]x',y'[$ are disjoint.

If $Q$ is a 2-transitive chain then $Y_Q$ is a vertex-transitive graph.

Let $D$ be an "open right" long line, so $D$ is locally order-isomorphic to the reals, for every $x$, the set $\{y\in D:y<x\}$ is order-isomorphic to $\mathbf{R}$ and every countable subset has an upper bound;

Let $X$ be obtained by concatenation $D\sqcup\{x_0\}\sqcup\mathbf{R}$ of a copy of $D$, a singleton $x_0$, and a copy of $\mathbf{R}$.

I claim that $Y_X$ is not vertex-transitive. Indeed, if $x<x_0<y$, then any complete subgraph in $Y_X$ containing the vertex $(x,y)$ is countable. On the other hand, there is an uncountable complete subgraph (consider uncountably may disjoint nonempty open intervals in $D$).

Write $D=\bigcup D_\alpha$, ascending union of a chain of intervals all order-isomorphic to $\mathbf{R}$, and $X_\alpha=D_\alpha\cup\{x_0\}\cup\mathbf{R}$; then $X_\alpha$ is order-isomorphic to $\mathbf{R}$. Then $X=\bigcup X_\alpha$, and $Y_X=\bigcup Y_{X_\alpha}$, union of a chain of vertex-transitive subgraphs.

| cite | improve this answer | |
  • $\begingroup$ Lovely example, nicely written down - thanks! $\endgroup$ – Dominic van der Zypen May 7 '18 at 13:07
  • 1
    $\begingroup$ I'd like a countable example, anyway. $\endgroup$ – YCor May 8 '18 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.