Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
If you consider the vertices (nodes) as labelled (i.e. distinguishable), this is pretty easy. What's tough is figuring out how many nonisomorphic graphs there are (up to permutation of the nodes). Given that this homework, I suspect the first interpretation was meant (labelled nodes). –  hardmath Apr 5 '12 at 17:35
    
Take a look at "Graphical enumeration" Frank Harrary –  Norbert Apr 5 '12 at 17:52

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
So each set {u, v} represents one edge, so there are nC2 ways to pick edges. Does that correspond to the number of possible graphs there are? –  roboguy12 Apr 5 '12 at 18:46
    
Definitely not! You have to go through the yes/no process for each pair. For each pair, there are two choices, connect or not. So the number of labelled loopless undirected graphs is $2^{\binom{n}{2}}$. Lots! –  André Nicolas Apr 5 '12 at 18:49
    
Oh! Ok, I wasn't sure what you had meant by the yes/no process. So, for directed, since {u, v} and {v, u} no longer correspond the same edge, the answer would be the same, only it would be the combination with repetition, right? –  roboguy12 Apr 5 '12 at 18:58
    
I don't think of it as combination with repetition. In my definition of directed graph, we have for each unordered pair $\{u,v\}$ $4$ choices: (1) No arrow; (2) arrow from $u$ to $v$, but not the other way; (3) same, except interchange $u$ and $v$; (4) two-way arrow. Then the number is $4^{\binom{n}{2}}$. If your definition of irected graph forbids two-way streets, need a minor modification. –  André Nicolas Apr 5 '12 at 19:08
    
Ugh, ok I just need to adjust my thinking of this. Of course this makes sense because since a line from $u$ to $v$ is different from a line from $v$ to $u$ it should be counted twice. I think I was thinking of something along the lines of having only two-way arrows, but thank you, you have been a wonderful help! –  roboguy12 Apr 5 '12 at 19:23

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!).

share|improve this answer
    
For either a directed or undirected graph WITH loops, there can be an infinite number of graphs, because you can always add an infinite number of loops, right? So the number of possible graphs with n vertices is found by n!, because not repeating vertices, at vertex v_i, you have n-i possible vertices left? Is that the right thinking, or am I completely off? –  roboguy12 Apr 5 '12 at 17:49
    
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.) –  Matt Pressland Apr 5 '12 at 18:26

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<b$ 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.