Countable Ultrahomogeneous Undirected Graphs

Abstract

Let $G = \left \langle {{V_G}, {E_G}} \right \rangle$ be an undirected graph. The complementary graph $\tilde G$ is $\left \langle {{V_G}, {E_{\tilde G}}} \right \rangle$ where $({V_1}, {V_2}) \in {E_{\tilde G}}$ iff ${V_1} \ne {V_2}$ and $({V_1}, {V_2}) \notin {E_G}$. Let $K(n)$ be the complete undirected graph on n vertices and let E be the graph [ill] i.e. $\left \langle {\{ a, b, c\} , \{ (b, c), (c, b)\} } \right \rangle$. G is ultrahomogeneous just in case every isomorphism of subgraph of smaller cardinality can be lifted to an automorphism of G. Let $\mathcal {D} = \{ K(n): n \in \omega \} \cup \{ E, \tilde E\} \cup \{ \tilde K(n): n \in \omega \}$. Theorem: Let ${G_1}$, ${G_2}$ be two countable (infinite) ultrahomogeneous graphs such that for each $H \in \mathcal {D} H$ can be embedded in ${G_1}$, just in case it can be embedded in ${G_2}$. Then ${G_1} \cong {G_2}$. Corollary: There are a countable number of countable ultrahomogeneous (undirected) graphs.