I dont know about that. I found the answer through logic rather than exact example. If a teacher shook hands with an odd number, x, of other teachers. That means that we know there were at least x handshakes that werent his, by symmetry of handshakes. Now, we know that those x handshakes could be divided up into any such partitions between teachers. But whats really cool is that we know some basic properties of partitions of odd numbers. We know that an odd number always breaks into an odd number of odd partitions (carrying the oddness.. ie. The extra 1 mod 2, the bit) You may need a few examples to convince yourself. 9=3+3+3 7=2+5 and well any number 199=196+1+1+1

Now clearly if the main teacher having odd shakes x, implies that an odd number of other teachers have odd total shakes, then the total odd shakers is even.