# Math Help - question in math logic

1. ## question in math logic

If we have K_n denote the complete graph on n vertices, can any one explain to me how to know how many substructures does K_n have?

2. Originally Posted by Mike12
If we have K_n denote the complete graph on n vertices, can any one explain to me how to know how many substructures does K_n have?
What do you mean by substructure?

3. If B is a set, then A ⊂ B means that A is a subset of B.
If N is a structure, then M ⊂ N means that M is a substructure of N.

4. Originally Posted by Mike12
If B is a set, then A ⊂ B means that A is a subset of B.
If N is a structure, then M ⊂ N means that M is a substructure of N.
So in this context, a substructure would be a subgraph of $\mathcal{K}_n~?$.

Are these labeled or unlabeled graphs?

5. there is no thing about labeled or unlabeled graph , all what I have in the question is a complete graph

6. If N is a structure, then M ⊂ N means that M is a substructure of N.
And what does ⊂ mean when applied to two structures? After all, structures are not just sets; they are tuples consisting of the domain together with functions and/or relations. Therefore, the regular concept of set inclusion cannot be applied to structures, and a specific definition is needed.

According to Wikipedia, M is a substructure of N if the domain of M is a subset of the domain of N and the relations of M are the corresponding relations of N restricted to the domain of M. A subgraph is a not necessarily a substructure because it may fewer edges than what is inherited from the large graph. Subgraphs are called weak substructures. So, a relevant question about this problem is, are we talking about regular or weak substructures? Or what is the definition of a substructure?

7. I think in this question it means subgraph

8. Originally Posted by Mike12
I think in this question it means subgraph
If we have $N$ vertices then $\mathcal{K}_N$ has $\dbinom{N}{2}$ edges.

There are $\displaystyle 2^{\binom{N}{2}}$ possible subgraphs of $\mathcal{K}_N$.
(That counts the empty-edge subgraph).

Would tell us what textbook you are following?

9. It is (mathematical logic) , so you told me that there are two to the power N choose 2 possible subgraphs.

10. Originally Posted by Mike12
It is (mathematical logic) , so you told me that there are two to the power N choose 2 possible subgraphs.
I answered a Graph Theory problem.
I have no idea how that relates to mathematical logic. You seem to refuse to answer a simple question about the text material. If you tell us about the textbook, one of us may have a better idea as to what you are doing. Until then, I done with it.

11. sorry but I do not refuse to answer you about textbook , the text book is ( Mathematical logic).