n-vertex graph

**Showcase_22** · November 24th 2009, 08:21 AM

I'm having trouble applying it!

**Plato** · November 24th 2009, 09:43 AM

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)} }$

**Showcase_22** · November 25th 2009, 08:57 AM

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!

**Plato** · November 25th 2009, 09:05 AM

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.

**Showcase_22** · November 25th 2009, 09:51 AM

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.

**Plato** · November 25th 2009, 10:37 AM

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

Thread: n-vertex graph

LinkBack

Thread Tools

Display

n-vertex graph

Similar Math Help Forum Discussions

Central and Bicentral vertex in graph

[SOLVED] graph vertex colouring

vertex basis for the graph

Finding the vertex of the parabolic graph

How to find vertex of a graph or equation

Search Tags