[croes]

Isn't the simplest solution that everybody shakes hand with Byron?

Everybody but Byron has one handshake and Byron has n-1, with n the number of people

[bitslayer]

Depending on your definition of simpler, everyone could just pair off and shake exactly one hand.

[xboxnolifes]

It's the simplest option when n is even (which it is in this case), but fails when n is odd.

[lupire]

The article about how this problem is trivial for N even but impossible for N odd.

[vlovich123]

The article is talking about the biggest odd subgraph within the even subgraph solution.

I think the problem with the suggestion is that the solution to the even subgraph may not be under your control? Not sure.