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 '12 at 9:22
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.