# Simple graphs (edges, nodes etc.)

1. Draw all possible graphs that can be constructed from the vertices $V_1=\{a,b,c\}$. Answer: Pic: I believe this is all of them (bottom three are all the same).

• How many such graphs have no edges? Answer: $1$.

• How many such graphs have exactly one edge? Answer: $3$.

• How many such graphs have exactly two edges? Answer: $3$.

• How many such graphs have all three edges? Answer: $1$.

• How many total graphs are there? Answer: $8$.

Now consider a vertex set of size $4$, $V_2 = \{a, b, c, d\}$.

2. How many possible edges exist over $V_2$? Answer: $C(4,2) = 6$.

3. How many unique graphs can be constructed from $V_2$? Hint: In any such graph, each edge is either present or absent. Answer: 4 2-way choices 2^4 = 16

4. How many unique graphs can be constructed from $V_2$ with exactly three edges? Hint: One must choose where to place the three edges.

Now generalize these results for a vertex set of size $n$, i.e., $V_3 = \{a, b, c,\dots,a_n\}$ where $|V_3| = n$.

5. How many possible edges exist over $V_3$?

6. How many unique graphs can be constructed from $V_3$? Justify your answer.

7. How many unique graphs can be constructed from $V_3$ using exactly $k$ edges? Justify your answer.

Please let me know if my answers for the first few are correct and any help is appreciated with the rest!! Thanks!!

-
The three triangles at the bottom of the linked picture are in fact all the same graph, just drawn in three different ways. –  Brad Dec 4 '11 at 18:32
The first question is ambiguous as written. I think the most natural interpretation would be "draw all graphs G such that the set of vertices of G is {a,b,c}". If this is the intended interpretation, then there is exactly one graph that has no edges. Remember, a graph doesn't need to be connected! –  Brad Dec 4 '11 at 18:35
Just a suggestion: Please avoid asking too many questions in one post. Identify what you find difficult in this problem and ask one (or a few related) suitable question that addresses that difficulty. –  Srivatsan Dec 4 '11 at 18:52
All the questions are ambiguous insofaras "possible graph" and "unique graph" may be variously defined. A "simple graph" does not allow self-edges (loops) and has only undirected edges. The picture linked in the question suggests this was intended. However in giving a set of vertices for the graph, the interpretation of a vertex-labelled graph is suggested. With that context, there are three distinct possibilities for the two-edge vertex-labelled graphs on $V_1 = \{a,b,c\}$, but these are isomorphic as unlabelled simple graphs. –  hardmath Dec 4 '11 at 18:56

I agree with Brad on the intended interpretation of the question. This means, as he said, that there is only one graph with no edges; if you think of the entire top row of your picture as one graph, that’s it. It also means that each of the three one-edge graphs in your second row is missing a vertex. The first, for instance, should be

                       a *--------* b             * c


As Brad said, the three graphs in your bottom row are all the same graph, merely drawn differently. Thus, you should have a total of eight graphs, one with no edges, three with one edge each, three with two edges each, and one with three edges.

Now look at the hint in question (4), but apply it to these graphs: there are $3$ possible edges, $ab, bc$, and $ac$, and in any given graph on the vertex set $\{a,b,c\}$ each of these edges can be either present or absent. Thus, for each of the three edges you have a two-way choice when constructing a graph: keep the edge, or discard it. For instance, keeping $ab$ and discarding the other two yields the graph that I drew above. How many ways are there to make $3$ $2$-way choices? $2\cdot 2\cdot 2=2^3=8$, right? That’s why there are $8$ graphs on the vertex set $\{a,b,c\}$. Now try applying this logic to question (4).

Notice also that we could have counted the two-edge graphs on $\{a,b,c\}$ by asking how many ways there are to pick $2$ of the $3$ possible edges to keep. How many ways are there to pick $k$ things from a collection of $n$ different things? That idea should carry you through the rest of the questions.

Added in response to comments/questions: Yes, there are $\binom{n}2$ possible edges over $V_3$. Each pair of vertices is a possible edge, and from an $n$-element set you can make $\binom{n}2$ distinct pairs. To make a graph with vertex set $V_3$, you must choose to keep some subset of these $\binom{n}2$ possible edges. A collection of $\binom{n}2$ things has $2^{\binom{n}2}$ possible subsets, so there are $2^{\binom{n}2}$ possible graphs with vertex set $V_3$, not $2^n$. (This is the same mistake that you made in question (4).)

For question (8) you want to make graphs with $k$ edges. There are as many of these as there are ways to choose $k$ of the $\binom{n}2$ possible edges. This is not $\binom{n}k$; what is it?

-
4. 2^4 = 16 5. c(6,3) = 20 (obviously wrong since there are only 16 possible graphs..) help? –  No Name Dec 4 '11 at 19:19
@NoName: No, $20$ is fine: it’s the $2^4$ that’s wrong. There are $6$ possible edges, not $4$, so there are $2^6=64$ possible graphs. –  Brian M. Scott Dec 4 '11 at 19:25
Ah, right thanks. So 6. C(n,2) , but why does this work? 7. 2^number of edges 8. C(number of edges,k) Are these right? –  No Name Dec 4 '11 at 19:35
@NoName: See revised answer. –  Brian M. Scott Dec 4 '11 at 19:45
Yes, I caught my errors right after i posted that comment. so wouldn't my corrected answers be correct? 6. c(n,2) 7. 2^ c(n,2) 8. C (c(n,2),k) –  No Name Dec 4 '11 at 19:49