universal graph Show that there doesn't exist a (countable) universal graph for each of the following classes of graphs (that is, no universal graph for class 1, and unrelatedly, no universal graph for class 2):


*

*All graphs that do not contain the countable complete graph.

*All graphs where the degree of each vertex is finite.
So a proof would involve showing that for every graph $G$ in one of these class, there is a graph in that same class $G'$ that is not isomorphic to some induced subgraph of $G$. How would I go about doing this? I know of the Rado random graph, which contains every countable graph as an induced subgraph, what fails in the two classes above (as opposed to all countable graphs) to make it so that there is no universal graph?
 A: Hint for #1: Suppose that $G_0$ is the purported graph, which contains any graph $H$ unless $H$ in turn contains $K_\omega$, the complete countable graph. Make a new graph, $G'_0$, by appending a new vertex $v_0$ to $G_0$ and adding edges from $v_0$ to every vertex of $G_0$. Then $G'_0$ does not contain $K_\omega$ (you prove this), so by hypothesis there must be a copy of $G'_0$ strictly inside of $G_0$, which we can call $G'_1$, and $G'_1$ must have an analogous vertex $v_1\ne v_0$.

Now you fill in the rest.
A: For the second problem, suppose that $G$ is a universal countable locally finite graph, and let $V=\{v_n:n\in\omega\}$ be the vertex set of $G$. For each $n\in\omega$ define a function
$$f_n:V\to\omega:v\mapsto|\{w\in V:d_G(v,w)\le n\}|\;,$$
where $d_G(v,w)$ is the length of the shortest path from $v$ to $w$ in $G$. (Verify that the definition makes sense.) Then define
$$f:\omega\to\omega:n\mapsto f_n(v_n)+1\;.$$
Now build a countable locally finite graph $H$ as follows. Let $H_0$ be a copy of $K_1$, with vertex $u$. For $n\ge 1$ let $H_n$ be a copy of $K_{f(n)}$. Form $H$ by taking the disjoint union of the graphs $H_n$, $n\in\omega$, and for each $n\in\omega$ adding an edge from each vertex of $H_n$ to each vertex of $H_{n+1}$.
Without loss of generality assume that $H$ is an induced subgraph of $G$; clearly $u=v_n$ for some $n\in\omega$. Find a lower bound for $f_n(u)$ by considering how many vertices $w$ of $H$ satisfy $d_H(u,w)\le n$, and use this and the definition of $f$ to get a contradiction.
