[Math] Simple graphs (edges, nodes etc.)

discrete mathematicsgraph theory

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

Best Answer

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?

Related Question