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