- Fix n ≥ 3 to be an integer. How many graphs are there that aresub-graphs of Kn (assume that all nodes are different and included in the sub-graph)?

Thanks Brothers !

Printable View

- Dec 7th 2012, 10:41 AMkakatomyQUESTION about complete graph
- Fix n ≥ 3 to be an integer. How many graphs are there that aresub-graphs of Kn (assume that all nodes are different and included in the sub-graph)?

Thanks Brothers !

- Fix n ≥ 3 to be an integer. How many graphs are there that aresub-graphs of Kn (assume that all nodes are different and included in the sub-graph)?
- Dec 7th 2012, 11:00 AMPlatoRe: QUESTION about complete graph
I not sure that I understand that statement.

There are $\displaystyle 2^n-1$ non-empty subsets of vertices.

If we chose a subset of vertices and include any edge between any two of them, then that is the number of sub-graphs.

Now some authors do not allow single vertex sub-graphs.

In that case we use the number $\displaystyle 2^n-n-1.$ - Dec 14th 2012, 10:40 PMskeptopotamusRe: QUESTION about complete graph
Hi, if that is the wording of your problem, with the "fix $\displaystyle n \geq 3$," then I think something is missing, because the solution does not depend on $\displaystyle n \geq 3$ at all. Do you mean connected subgraphs? Do you include the order-zero graph?