5
$\begingroup$

I'm kind of stuck on this homework problem, could anyone give me a springboard for it?

If we have $n\in\mathbb{Z}^+$, and we let the set of vertices $V$ be a set of size $n$, how can we determine the number of directed graphs/undirected graphs/graphs with loops etc.? Is there a formula for this? I feel like it can be done using combinatorics but I can't quite figure it out. Any ideas?

Thanks!

  • 0
    it is possible the homework is asking for the answer of number of "random graphs" disregarding identical graphs, a simpler answer using the powerset of combinatorial C(n,2). a correct answer involves [graph isomorphism](http://en.m.wikipedia.org/wiki/Graph_isomorphism).2014-09-04

3 Answers 3

4

A start: We will show how to count labelled, loopless, undirected graphs. There are $\binom{n}{2}$ ways to choose a set $\{u,v\}$ of two vertices. For every such set, we say yes or no depending on whether we have decided to join $u$ and $v$ by an edge. Alternately, but somewhat less concretely, let $P$ be the set of all (unordered) pairs. This set $P$ has cardinality $\binom{n}{2}$. To specify a loopless undirected graph, we choose a subset of $P$ and connect any unordered pair in that subset by an edge. How many subsets does $P$ have?

To extend to graphs with possible loops (but at most one per vertex) there is a similar yes/no process.

  • 0
    To add to my answer, if loops are possible, but at most one loop from $v$ to $v$, multiply the loopless answer by $2^n$.2012-04-05
1

For labeled vertices:

To count undirected loopless graphs with no repeated edges, first count possible edges. As Andre counts, there are $\binom{n}{2}$ such edges. One by one, each edge is either included or excluded. So this gives $2^{\binom{n}{2}}$ possible graphs.

If loopless graphs with no repeated edges are directed, each pair of vertices $a provides $3$ possibilities for a (potentially absent) edge. Do you see what they are and how that modifies the count?

If there are loops (but still no repeated edges), then either of the above scenarios are modified by realizing that there are $n$ more pairs of points to consider - the ones where $a=b$. Do you see how this would modify the count of graphs? Watch out - it doesn't really make sense to count a loop as directed.

0

Without some restrictions, there are infinitely many, so I suspect you at least have the assumption that you can't have more than one edge between a single pair of vertices.

You should think about what the maximal number of possible edges you could have is in a graph with $n$ vertices (this is why we should assume no multiple edges, so the number is finite, but it will be different depending on whether you allow loops or not). Then to specify a particular graph on $n$ vertices, you need to specify whether each of the possible edges appears in your particular graph or not. If your graph should be oriented, you then have the additional choice of which way the edge should point. You should then be able to ennumerate the total number of possible choices (if you can't, let me know and I'll add more detail here - as this is tagged homework I don't want to give too much away immediately!).

  • 0
    I'm counting more than one loop on the same vertex as being a multiple edge, so you're capped at one per vertex. But if you allow infinitely many loops then yes. (Possibly you are taking "loop" to be what I would call "cycle" - to me a loop is an edge from a vertex to itself). I'm not sure what you mean by not repeating vertices - what type of graphs are you trying to count? If it's just any graphs on $n$ labelled vertices then something isn't right. Maybe it would help to think of an edge as a pair of ordered vertices? (And a directed edge as an ordered pair.)2012-04-05