So I'm studying graph theory at the moment and would like some constructive criticism or thoughts on my method. The problem can be formulated as follows. I'm looking for someone to verify my answer as well.


John and Jane were at a party with three other couples; determine how many people John and Jane, respectively, greeted with if following rules applies:

$1$: No one greeted their partner.

$2$: No one greeted the same person more than once.

Jane, for some reason, asked the other $7$ people how many other people they had greeted at the end of the party, and they all answered differently.

My solution

Let $G=(V,E),\quad |V|=8$. Also let $n_1$ denote Jane's grade (as a node).

The rest can be denoted as $n_2,n_3,\cdots,n_8.$ We know that $n_i\not=n_j$ iff $i\not=j$ and $i,j\in\mathbb{Z}_+$ Hence, $n_2$ through $n_8$ can be chosen randomly with the limitations, since it does not matter in the end:

$\begin{cases} n_2=6\\ n_3=5\\ n_3=4\\ n_5=3\\ n_6=2\\ n_7=1\\ n_8=0 \end{cases}$

From this we get the following graph:simple graph

Now the logic here is not too hard to explain. Starting with $n_2$ we know she/he must connect to 6 different nodes, but not $n_8$ as it equals $0$. This logic is iterated until graph is complete.

Jane greeted $3$ other people; and John greeted $0,1,2,$ or $3$ people.

The Jane part is a sure thing, however, I'm a little uncertain about John. Appreciate all comments, thanks.

Edit 1: Figured out that $n_5$ must be John, because $n_8, n_7,n_6$ are partners with $n_2,n_3,n_4$ respectively.

John greeted $3$ people.

I suppose this "question" can be good for viewers in the future as well.

  • 1
    $\begingroup$ My one criticism is that it's not at all obvious who is whose partner in your graph. $\endgroup$ – genisage Sep 30 '14 at 21:23
  • $\begingroup$ What would you, personally, do to improve this? I agree with you on that, as it made me miss the trivial answer to how many John greeted. $\endgroup$ – B. Lee Sep 30 '14 at 21:26
  • 1
    $\begingroup$ I would choose four colours and give two vertices the same colour if they're partners. $\endgroup$ – genisage Sep 30 '14 at 21:28

Your Answer

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

Browse other questions tagged or ask your own question.