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?

Printable View

- Mar 4th 2011, 07:56 AMMike12question 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?

- Mar 4th 2011, 07:59 AMPlato
- Mar 4th 2011, 09:23 AMMike12
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. - Mar 4th 2011, 09:47 AMPlato
- Mar 4th 2011, 10:20 AMMike12
there is no thing about labeled or unlabeled graph , all what I have in the question is a complete graph

- Mar 4th 2011, 11:29 AMemakarovQuote:

If N is a structure, then M ⊂ N means that M is a substructure of N.

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? - Mar 5th 2011, 01:16 PMMike12
I think in this question it means subgraph

- Mar 5th 2011, 01:38 PMPlato
If we have $\displaystyle N$ vertices then $\displaystyle \mathcal{K}_N$ has $\displaystyle \dbinom{N}{2}$ edges.

There are $\displaystyle \displaystyle 2^{\binom{N}{2}}$ possible subgraphs of $\displaystyle \mathcal{K}_N$.

(That counts the empty-edge subgraph).

Would tell us what textbook you are following? - Mar 5th 2011, 02:41 PMMike12
It is (mathematical logic) , so you told me that there are two to the power N choose 2 possible subgraphs.

- Mar 5th 2011, 03:05 PMPlato
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. - Mar 5th 2011, 03:35 PMMike12
sorry but I do not refuse to answer you about textbook , the text book is ( Mathematical logic).