0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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$? $\endgroup$
    – JMoravitz
    Dec 2, 2017 at 4:01
  • $\begingroup$ The complement of G has 19 edges $\endgroup$
    – JRob
    Dec 2, 2017 at 4:01
  • $\begingroup$ 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$? $\endgroup$
    – JMoravitz
    Dec 2, 2017 at 4:03
  • $\begingroup$ 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? $\endgroup$
    – JRob
    Dec 2, 2017 at 4:07
  • $\begingroup$ 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. $\endgroup$
    – JMoravitz
    Dec 2, 2017 at 4:10

1 Answer 1

Reset to default
4
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Thanks. Edited. $\endgroup$
    – Noah Singer
    Dec 2, 2017 at 5:41
  • $\begingroup$ 36 vertices???? $\endgroup$
    – William Elliot
    Dec 2, 2017 at 7:50

You must log in to answer this question.

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