discrete mathematics
So G is a simple graph, the complement of G, denoted G' is obtained as follows:
The vertex set of G' is identical to the vertex set of G. However 2 distinct vetices v and w of G' are connected by an edge if and only if, v and w are not connected by an edge in G. How can we find the compliment of the above graphs?
for a) am I suppose to draw a graph with 4 edges that doesn't overlap with that original graph?
Same goes for b), so v1 – v4 and v2- v3 ?
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?
...in a directed graph, what makes it non isomorphic?
As an adjective for an individual graph, non-isomorphic doesn't make sense. You can't sensibly talk about a single graph being non-isomorphic. What we can talk about are sets of graphs which are pairwise non-isomorphic (i.e., any two graphs in the set are not isomorphic).
Intuitively speaking, two graphs $G$ and $G'$ are isomorphic if they have essentially the same structure (and non-isomorphic otherwise). Formally, two graphs are isomorphic if there's an edge-preserving bijection from the vertices of $G$ to the vertices of $G'$.
In the following example, the two red digraphs have essentially the same digraph: there is one node with two out-edges. An edge-preserving bijection (i.e., an isomorphism) in this case is $1 \mapsto 2$, $2 \mapsto 1$ and $3 \mapsto 3$.
There is no such bijection between the red and blue digraphs since they do not have the same in/out-degree sequences.
Is a set of vertices all isolated included? (some solutions say yes, but how can it then be called 'directed?')
The $n$-vertex null digraph (i.e. $n$ vertices and no edges) is consistently regarded as a directed graph.
How many nonisomorphic directed simple graphs are there with n vertices, when n is 2,3, or 4?
To answer this question requires some bookkeeping. The $2$-node digraphs are listed below. Note that I'm including the possibility of bidirectional edges (i.e., an edge from $A$ to $B$ and an edge from $B$ to $A$).
The number of digraphs grows quickly, and is given by Sloane's A000273. For $2$-, $3$- and $4$-node digraphs, the numbers are $3$, $16$, and $218$, respectively (allowing bidirectional edges).
If I was pressed to find these numbers, I'd get my computer to find them by:
This would be quite an inefficient generation method, but would be fast enough for $4$-node digraphs.
Can there be multiple graphs in the answer that have the same number of edges and the same in/ out degree totals, or does a distinct signature of edge # and in/ out degree total constitute a distinct graph?
There can be, here's an example:
and one without bidirectional edges:
In the table in the question there's a number of omissions (this is why I'd do it on a computer).
You've correctly observe e.g. that:
are not isomorphic, since the in/out-degrees don't match. For the same reason e.g.:
are also non-isomorphic. Similar omissions (where we flip edge directions) happen in other cases.
I also don't see a oriented 3-cycles with an isolated vertex.
Note: Sloane's A001174 asserts there are 42 digraphs on 4 vertices.
Best Answer
This is just a direct application of the definition of compliment.
For the first graph, G' has edges v1-v3 and v4-v3
and the second graph, G' has edges v1-v4, v1-v3, v2-v4, and v2-v3