# Finding vertices of a simple graph

Not sure how to go about solving this. If anyone has a hint on how to start this, that would be great!

If G is a simple graph with no self-loops with 17 edges and complement of G has 19 edges, how many vertices does G have? Explain how you got your answer.

• Wait... so how many edges does $G$ have? 17? or 19? You said two different things in the same line. Is it that $G$ has $17$ edges and something else has $19$ edges? What is that something else? The line graph of $G$? The graph complement of $G$? Dec 2, 2017 at 4:01
• The complement of G has 19 edges
– JRob
Dec 2, 2017 at 4:01
• You should correct your post then with that information. Now that that ambiguity is out of the way, what do you know about what a graph complement is? If we were to consider the union of the edge set of $G$ with the edge set of the complement of $G$, what type of graph does that make? How many edges does it have? If it has $n$ vertices, how many edges does it have in terms of $n$? Dec 2, 2017 at 4:03
• The graph complement is the edges that are not in G so if G has 17 edges this would mean that there are 19 ways that G is not connected?
– JRob
Dec 2, 2017 at 4:07
• That is not what I was trying to get at. $G$ has some edges and $G'$ (what I'll use to denote the complement of $G$) has all of the edges that $G$ doesn't have and none of the edges that $G$ does have. If we were to combine $G$ and $G'$ by taking the graph union, then we have all possible edges for our vertices, what is called a complete graph. Dec 2, 2017 at 4:10

We know that, when we join $G$ and its complement together, we have a complete graph with $17 + 19 = 36$ edges. Since in a complete graph all vertices are connected and therefore $|E| = |V|(|V|-1)/2$, we know that $|V| = 9$.
Now, we'll construct one such graph. Consider a graph with $9$ vertices arranged in a circle, with every vertex connected to every vertex that's either 1 or 2 away in the circle. This graph has $18$ edges. Remove an arbitrary one, and there's your $17$.