The complement of a simple undirected graph $G$, denoted $G'$, has the same vertices as $G$ where two vertices in $G'$ are adjacent if and only if they are not adjacent in $G$.

(a) Describe the graph $C_n'$.
(b) Describe the graph $K_n'$.
(c) If $G$ is a simple graph with $15$ edges and $G'$ has $13$ edges, how many vertices does $G$ have?

for a) I said its impossible because all vertices are connected to edges and for b) I said it should be $K_n$ but not sure what the answer should be for c).

Can anyone help please?


To get the complement of a simple graph $G$, look at each pair of vertices: if they are adjacent in $G$, there is not an edge between them in $G'$, and if they are not adjacent in $G$, then there is an edge between them in $G'$.

Let’s look at (b) first: it’s the easiest. In the graph $K_n$ every vertex is adjacent to every other vertex: there are no vertices $u$ and $v$ such that $u$ is not adjacent to $v$. Therefore no two vertices are adjacent in $K_n'$: $K_n'$ is the graph with $n$ vertices and no edges.

Next we’ll tackle (c). $G$ and $G'$ have the same set of vertices; call it $V$. If $u$ and $v$ are two of these vertices, they are adjacent in exactly one of $G$ and $G'$. In other words, there is an edge between them in $G$ or in $G'$, but not in both. Thus, the number of pairs of vertices in $V$ is the same as the total number of edges in $G$ and $G'$, which is $15+13=28$. How many vertices must there be in $V$ if there are $28$ pairs of vertices. (HINT: More generally, how do you calculate the number of $2$-element subsets of a set of $n$ things?)

Now back to (a). I assume that $C_n$ is the cycle graph with $n$ vertices and $n$ edges. This one is quite a bit more complicated. I’m not sure that there is a really nice general description of $C_n'$; it’s what’s left if you start with $K_n$, find a cycle of length $n$ in $K_n$, and remove the $n$ edges in that cycle. You should at least try to work out what $C_3',$C_4'$, and $C_5'$ are, and $C_6'$ also isn’t hard to draw.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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