4
$\begingroup$

The axiom of choice is of no use when trying to prove that every vertex-transitive subgraph is contained in a maximal vertex-transitive subgraph, because a union of an ascending chain of vertex-transitive subgraphs need not be vertex-transitive.

Question. What is an example of a simple, undirected graph $G=(V,E)$ that contains no maximal vertex-transitive subgraph?

Precise formulation. For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x, y\in X\text{ and } x\neq y\big\}$. What is an example of a simple undirected graph $G=(V,E)$ such that for every subset $S\subseteq V$ with the property that the graph $(S, E\cap [S]^2)$ is vertex-transitive, there is a set $T\subseteq V$ with $T \neq S$ and $S\subseteq T$ such that $(T, E\cap [T]^2)$ is also vertex-transitive?

Improve this question
$\endgroup$
5
  • $\begingroup$ You possibly assume that $S \neq V$ in the precise formulation of the problem. $\endgroup$
    – Mahdi - Free Palestine
    Commented May 8, 2018 at 14:26
  • 2
    $\begingroup$ Mahdi, if the whole graph is vertex transitive, then it would be maximal. $\endgroup$
    – Joel David Hamkins
    Commented May 8, 2018 at 14:31
  • 1
    $\begingroup$ An observation: every graph has maximal indiscrete subgraphs -- subgraphs with no induced edges -- and these are vertex transitive. But they are not necessarily maximal with respect to being vertex transitive, and so this doesn't answer the question. $\endgroup$
    – Joel David Hamkins
    Commented May 8, 2018 at 14:46
  • 1
    $\begingroup$ I should have said "edgeless" subgraph, since I think "indiscrete" is not the right word for this. $\endgroup$
    – Joel David Hamkins
    Commented May 8, 2018 at 17:16
  • $\begingroup$ Thanks for your comments! - I understood right away what you meant by "indiscrete" and I often wonder whether there is some kind of functor (or weaker connection) between the category of topological spaces and the category of simple, undirected graphs, such that indiscrete spaces correspond exactly to edgeless graphs (and discrete spaces to complete graphs). $\endgroup$
    – Dominic van der Zypen
    Commented May 8, 2018 at 17:40

0

Reset to default

You must log in to answer this question.