Let's consider an undirected graph whose every vertex is either connected with every other vertex or with every vertex except exactly one.
(To avoid misunderstandings: The graph must be representation of a people in a party, who came either alone or with a partner. Edges are handshakes.)

Problem: The graph consists of 62 edges. How many vertices does it have?

My approach: Let's take a subgraph with no pairs (largest complete graph component) such that number of edges is less than 62, and then gradually add pairs.
So number of edges in complete graph with $n$ vertices is $\frac{n(n-1)}{2}$. Adding first pair brings $2n$ edges, next $2(n+2)$ etc. By bruteforce we have: $$\frac{4(4-1)}{2}+2*4+2*6+2*8+2*10=62$$
Hence $4+2+2+2+2=12$ vertices. Is it correct?
I really don't like my approach with bruteforce since I can't see if it's the only possible combination. In the lecture notes we have proven handshaking lemma, but I don't see where to apply it. Please let me know if you have a better solution.


Some vertices (say $k$) are connected to all the other vertices and the rest ($l$ so that $n=k+l$ is the total number of vertices) are connected to all the vertices but one (their partner), thus, there should be $\frac{k(k+l-1)}{2} + \frac{l(k+l-2)}{2}$ edges (remember how the $\frac{n(n-1)}{2}$ value you gave is found: each vertex, i.e. $n$ possibilities, is bound to all the other vertices, i.e. $n-1$ possibilities, and in an undirected graph, by doing that you counted each edge twice).

Therefore, what you want to solve is $\frac{k(k+l-1)}{2} + \frac{l(k+l-2)}{2}=62$. Catching up on your solution: for $k=4; l=8$, we indeed find 62 edges. Now that you have an explicit formula for the number of edges, you may easily find all the combinations (although this is still bruteforce).

The formula is exactly what the handshaking lemma would give you since there are $k$ vertices of degree $n-1$ and $n-k$ vertices of degree $n-2$.

  • $\begingroup$ No, not necessarily. The graph must be representation of a people in a party, who came either alone or with a partner. Edges are handshakes. $\endgroup$ – user3342072 Apr 13 '18 at 7:27
  • $\begingroup$ Ok, then what bugged is that there are nodes without a pair.That is why you first took the complete graph (representing all people coming alone) and then added the couples that came along (but do not shake hands with their respective partners). Am I right? $\endgroup$ – Bill O'Haran Apr 13 '18 at 7:46
  • $\begingroup$ Yes, you are absolutely right. I apologise for being unclear. $\endgroup$ – user3342072 Apr 13 '18 at 7:52
  • 1
    $\begingroup$ No problem, I'll edit my answer right away. I suggest you edit your question. $\endgroup$ – Bill O'Haran Apr 13 '18 at 7:53

The only solution is $n=12.$

If $n$ is the number of vertices and $k$ the number of pairs, then we must have $$2k\le n,$$ and the number of edges is $$\binom n2-k=62.$$ Thus we have $\binom n2=62+k\ge62,$ that is, $n(n-1)\ge124,$ and also $\binom n2=62+k\le62+\frac n2,$ which simplifies to $n(n-2)\le 124.$ The only integer solution of the inequalities $$n(n-2)\le124\le n(n-1)$$ is $n=12,$ and then $k=\binom{12}2-62=4.$


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.