2
$\begingroup$

Given some graph $G$ such that we have between two vertices an edge, and between each edge two distinct vertices. How many vertices do we have if there is a total of 196 edges?

I'm reproducing this question from memory but I think that's how the question was phrased. Now I suppose the last condition is to rule out edges from a vertex to itself, and the first condition is to rule out cases where the graph is disconnected. But hey, isn't that trivially just the complete graph $K_n$ with edges $n \choose 2$? But if that's so there then there has to be a problem with the number of edges given since there is no integral solution for the equation ${n \choose 2} = 196$.

Any pointers would be appreciated.

$\endgroup$
1
  • $\begingroup$ I think 196 may not be the correct number if you have a complete graph. $\endgroup$
    – AmFCG
    Nov 9, 2012 at 9:22

1 Answer 1

1
$\begingroup$

If when you say "we have between two vertices an edge" it means 'we have between two vertices at least one edge', you can choose any n such that ${n \choose 2} < 196$.

So the solution is any $n\le 20$ as ${20 \choose 2} = 190$ and there are 6 edges you can place anywhere if you choose $n=20$.

$\endgroup$

You must log in to answer this question.

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