I have no idea how to even begin or think about this. I was thinking of drawing out graphs with that many edges, but the possibilities for complements seem endless.
"Let G be a graph. Now let G'
be the complement graph of G. G' has the same set of vertices as
G, but two vertices x and y in G are adjacent only if x and y are not
adjacent in G
. If G has 15 edges and G'
has 13 edges, how many vertices does G
have? Explain."
Thanks guys
Best Answer
Notice that the sum of the number of edges in the original gragh $G$ and the complement graph $G'$ must be equal to the number of edges in a complete graph with the number of vertices being the number of vertices in $G$. This is because $G'$ will only contain edges not included in $G$.
Thus if the number of vertices in $G$ is $V$, then the total number of edges is $\frac{V(V-1)}{2}$. Since
$$ 15+13 = 28 = \frac{56}{2} = \frac{8(8-1)}{2} $$
Therefore there must be 8 vertices in the graph.