I'm having trouble applying it!

Printable View

- Nov 24th 2009, 08:21 AMShowcase_22n-vertex graph
I'm having trouble applying it!

- Nov 24th 2009, 09:43 AMPlato
For the sake of ease of notation, define $\displaystyle E(n)=\frac{n(n-1)}{2}$.

That is maximum number of edges in a simple graph on $\displaystyle n$ vertices.

Hence there are $\displaystyle 2^{E(n)}$ labeled simple graphs on $\displaystyle n$ vertices.

Now we must remove any of those graphs having null vertices.

$\displaystyle I(n) = \sum\limits_{k = 0}^n {\left( { - 1} \right)^k\binom{n}{k} \cdot 2^{E(n - k)} } $ - Nov 25th 2009, 08:57 AMShowcase_22
Just so i'm clear, is $\displaystyle I(n)$ the number of vertices?

Also, what about graphs that aren't simple? From the question, "without vertices of degree 0" as a definition for isolated vertices implies that we are dealing with simple graphs. However, it isn't explicitly stated! - Nov 25th 2009, 09:05 AMPlato
- Nov 25th 2009, 09:51 AMShowcase_22
so we still need to add on the number of non-simple graphs.

We could just have a graph where every point maps to itself, we have't included that yet. - Nov 25th 2009, 10:37 AMPlato
I have no idea what you are talking about there.

Do you understand of sort of graphs we are dealing with here?

Insofar as I know the*problem of counting labeled graphs*only comes up for simple graph.

Oddly enough it is easier to count labeled graphs then it is to count unlabeled graphs.

There is no ‘mapping’ involved in a graph itself.

So what sense does it make to say "where every point maps to itself"?