0
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .