"Fix $n \geq 3$ and let $K_n$ be the complete graph on $n$ vertices Let $\mathbb{K}_n$ be the class of all finite simple graphs that do NOT have $K_n$ as a subgraph.

Let $\Gamma_n$ be the Fraisse limit of $\mathbb{K}_n$. Show that $\Gamma_n$ is the unique graph such that:

  1. Every finite subgraph of $\Gamma_n$ is in $\mathbb{K}_n$, and
  2. If $X$ and $Y$ are disjoint finite sets of vertices of $\Gamma_n$, and $K_{n-1}$ is not embeddable in the restriction of $\Gamma_n$ to $X$, then there is a vertex in $\Gamma_n$ which is joined to every vertex in $X$ and to no vertex in $Y$."

I think I've solved Question 1, it seems quite straightforward. By definition, all (finite) induced subgraphs of $\Gamma_n$ will be in $\mathbb{K}_n$, and this can easily be extended to all subgraphs.

I'm not too sure how to approach Question 2, the condition "$K_{n-1}$ is not embeddable" is throwing me off. I'm thinking we have to use the fact that $\Gamma_n$ is homogeneous. I've proved that $\Gamma_n$ is regular, if that is of any help.

If needed, here's a definition of the Fraisse limit from Model Theory: "Let $L$ be a countable signature, and let $\mathbb{K}$ be a nonempty finite or countable set of finitely generated $L$-structure which has the Hereditary Property, Joint Embedding Property and the Amalgamation Property (see here for definitions). Then there exists an $L$-structure $\mathcal{D}$ (called the Fraisse limit of $\mathbb{K}$), unique up to isomorphism, such that

  • $\mathcal{D}$ is at most countable.
  • $\mathbb{K} = \text{age}(\mathcal{D})$; that is, $\mathbb{K}$ is the set of all finitely generated substructures of $\mathcal{D}$. Again, see here for a definition.
  • $\mathcal{D}$ is homogeneous; that is, any isomorphism between finitely generated substructures of $\mathcal{D}$ extends to an automorphism of $\mathcal{D}$."

In the language of graphs, an $L$-structure is a graph, and a finitely generated substructure is an induced subgraph.

Thank you!


1 Answer 1


I'll explain why $\Gamma_n$ satisfies property 2.

Suppose $X$ and $Y$ are disjoint subsets of $\Gamma_n$ and $K_{n-1}$ is not embeddable in the induced subgraph on $X$. Let $G$ be the induced subgraph on $X\cup Y$, and let $H$ be the graph obtained from $G$ by adding a single new vertex $v$ and new edges connecting $v$ to every element of $X$ (but no element of $Y$). Then you can check that $K_n$ is not embeddable in $H$.

So $H\in \mathbb{K}_n$, and hence there is an embedding $f\colon H\to \Gamma_n$. Let $g\colon G\to \Gamma_n$ be the restriction of $f$ to $G$. Then $g\colon G\to f(G)$ is an isomorphism, so it extends to an automorphism $\sigma\colon \Gamma_n\cong \Gamma_n$. Let $w = \sigma^{-1}(v)$. Then we have $wEx$ for all $x\in X$ and $\lnot wEy$ for all $y\in Y$.

So now you know that $\Gamma_n$ satisfies properties 1 and 2. Of course, you're not done with the problem - you still need to show that $\Gamma_n$ is the unique (countable!) graph satisfying properties 1 and 2. Hint: use a back-and-forth argument.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .