MHB How Many Unique Substructures Exist in an n-Clique?

[Andrei1]

Let $$K_n$$ be the $$n$$-clique for some $$n\in\mathbb{N}$$. Then any graph having at most $$n$$ vertices is a subgraph of $$K_n$$.
(a) How many substructures does $$K_n$$ have?
(b) How many substructures does $$K_n$$ have up to isomorphism?
(c) How many elementary substructures does $$K_n$$ have?

My answers:
(a) $$2^n$$
(b) $$n$$
(c) $$2^n$$
Are they correct?

 

[caffeinemachine]

My answers:
(a) $$2^n$$
(b) $$n$$
(c) $$2^n$$
Are they correct?

If by substructures you mean subgraph, then the answer to part (a) looks okay. Some people may write $2^n-1$ because they might not want to include $\emptyset$ in the list.

For the second, is the question asking to find out the number of graphs, up to isomorphism, having at most $n$ vertices. In that case, the answer cannot be just $n$.

For part (c), I don't know the definition of elementary substructures. Can you please define it?

 

[Andrei1]

$$M$$ is a substructure of $$N$$ ... if
1. $$M$$ is a structure having the same vocabulary as $$N$$,
2. the underlying set $$U_M$$ of $$M$$ is a subset of the underlying set $$U_N$$ of $$N$$, and
3. $$M$$ interprets the vocabulary in the same manner as $$N$$ on $$U_M$$.

Let $$N$$ and $$M$$ be structures in the same vocabulary. Then $$M$$ is an elementary substructure of $$N$$ ... if and only if the identity function $$id\colon M\to N$$ defined by $$id(x)=x$$ is an elementary embedding [preserves all formulas].

About (b). Let's take a 4-clique. Any subgraph of it is not a substructure if it is not a clique. So I have, up to isomorphism, 4 substrucutures: one 1-clique, one 2-clique, ...

 

[caffeinemachine]

About (b). Let's take a 4-clique. Any subgraph of it is not a substructure if it is not a clique. So I have, up to isomorphism, 4 substrucutures: one 1-clique, one 2-clique, ...

Then by substructures you do not means subgraphs. It's fine then.