A connected (and infinite) graph $U$ will be called $n$-universal if any connected graph with degree $\leqslant n$ admits an embedding in $U$.
Is there a 3-universal graph with bounded degree?
$\begingroup$
$\endgroup$
25
asked Jan 22 at 17:16
-
2$\begingroup$ @AlessandroCodenotti Nope - every connected bounded-degree graph is countable (I made exactly this mistake, multiple times, earlier). $\endgroup$– Noah SchweberCommented Jan 22 at 18:30
-
3$\begingroup$ Not Noah, but if you fix a starting vertex $v$ and, at step $i$, collect all neighbors of the vertices you have so far, then you will exhaust the graph in countably-many steps with only finitely many vertexes added at each step. EDIT: If I'm not mistaken, the same argument establishes countability if you only assume that each vertex has finite degree. $\endgroup$– Ben JohnsrudeCommented Jan 22 at 18:32
-
2$\begingroup$ Dangit, I had stuff to do today ... $\endgroup$– Noah SchweberCommented Jan 22 at 18:35
-
2$\begingroup$ @CorentinB NOT induced. $\endgroup$– Anton PetruninCommented Jan 22 at 18:40
-
3$\begingroup$ @CommandMaster we aren't assuming that the graphs are finite, so there are uncountable many graphs we need to embed in $U$. $\endgroup$– Ben JohnsrudeCommented Jan 22 at 19:01
|
Show 20 more comments
1 Answer
$\begingroup$
$\endgroup$
5
I think that the answer is negative.
Assume that such graph $G$ on the vertex set $\{v_1,v_2,\ldots\}$ exists. We construct our not-embeddable graph $H$ on $\{1,2,\ldots\}$ by steps. On the $i$-th step only finitely many edges are added to $H$, it is connected and has degrees at most 3, and there is no embedding of this finite graph $H_i$ to $G$ for which $1$ goes to $i$. I explain how to do the first step, all other are essentially the same.
We take a long path $P=1-2-\ldots -(6N)$ and partition the $2N$ vertices $2,5,\ldots,6N-1$ by pairs arbitrarily. We get $(2N-1)!!$ different labelled graphs. How much of them are embeddable to $G$ so that 1 goes to $v_1$? We should start with a path of length $6N-1$ from $v_1$ (exponentially many possibilities), which should be the image of $P$, then $G$ induced to $P$ has linearly many edges, and thus exponentially many subsets of these edges. So, only exponentially many such graphs are embeddable to $G$, and we may perform the first step.
answered Jan 22 at 19:51
-
1$\begingroup$ Well, that explains why I was having trouble proving a positive answer! $\endgroup$ Commented Jan 22 at 20:32
-
7$\begingroup$ To add a reference and some shameless self-promotion to this answer: this is Theorem 1.2 in my paper "A note on classes of subgraphs of locally finite graphs" $\endgroup$ Commented Jan 23 at 5:29
-
3$\begingroup$ @FlorianLehner only irrelevant self-promotion is shameful :) By the way, is your argument similar to this? $\endgroup$ Commented Jan 23 at 8:17
-
5$\begingroup$ Link to paper by Florian Lehner: A note on classes of subgraphs of locally finite graphs (DOI), J. Combin. Theory Ser. B 161 (2023), 52–62. $\endgroup$ Commented Jan 23 at 13:13
-
2$\begingroup$ @FedorPetrov it is fairly similar; essentially it also uses the fact that there are too many finite rooted graphs with maximum degree 3 to embed them with the root at some fixed vertex $\endgroup$ Commented Jan 23 at 21:09