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.

  • 0
    I think 196 may not be the correct number if you have a complete graph.2012-11-09

1 Answers 1

1

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