# n-vertex graph

• Nov 24th 2009, 09:21 AM
Showcase_22
n-vertex graph
I'm having trouble applying it!
• Nov 24th 2009, 10:43 AM
Plato
Quote:

Originally Posted by Showcase_22
Determine the number of n-vertex labelled graphs without isolated vertices (ie. without vertices of degree 0).

For the sake of ease of notation, define $E(n)=\frac{n(n-1)}{2}$.
That is maximum number of edges in a simple graph on $n$ vertices.
Hence there are $2^{E(n)}$ labeled simple graphs on $n$ vertices.

Now we must remove any of those graphs having null vertices.
$I(n) = \sum\limits_{k = 0}^n {\left( { - 1} \right)^k\binom{n}{k} \cdot 2^{E(n - k)} }$
• Nov 25th 2009, 09:57 AM
Showcase_22
Just so i'm clear, is $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, 10:05 AM
Plato
Quote:

Originally Posted by Showcase_22
Just so i'm clear, is $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!

$I(n)$ is the number graphs on n vertices with no isolated vertices( zero degree).

A non-simple graph is one with more than one edge between two vertices or contains a loop or could be a directed graph.
• Nov 25th 2009, 10:51 AM
Showcase_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, 11:37 AM
Plato
Quote:

Originally Posted by Showcase_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.

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"?