Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I think 196 may not be the correct number if you have a complete graph. –  user46090 Nov 9 '12 at 9:22

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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