Year 12s: what will be the first way you research your future options? >>

D1: Euler's hand-shaking leema

Kravez

Can anyone explain this? The wording within the textbook is ambiguous.

Thanks.

Reply 1

tania<3

The title of this thread made me go :lolwut:

What board is this on? I'm doing AQA D1 so never heard of this... lol

Reply 2

Blutooth

Original post by Kravez

Can anyone explain this? The wording within the textbook is ambiguous.

Thanks.

Let's call the people who shake hands an odd number of times Oddballs, and the other people Evies.

let

O_i

= the no. of handshakes the oddball numbered i makes.
let

E_i

= the no. of handshakes evie numbered i makes.

Let

B= \sum E_i

Then B is the the sum of handshakes made by all evies.
Let

C= \sum O_i

. Thus C is the the sum of handshakes made by all Oddballs.
Let

A=\sum O_i+ \sum E_i

. Then A be the the sum of handshakes made by every person.

Now we can show that A is even, since A double-counts the number of handshakes. If a handshake is made by (1,3) then we will have counted that handshake once for person 1 and another time under person 3. B is obviously even since each

E_i

is even. Thus

C

must also be even as

C=A-B

and

A

and

B

are even.

Remember

C= \sum O_i

. Now if the number of

O_i

were odd, then

C

would be the sum of an odd number of odd numbers and thus would be odd. This is a contradiction. Hence the number of

O_i

must be even- which is what Euler's theorem states.

(edited 11 years ago)

Reply 3

Jake22

Each edge in a graph is incident with precisely two vertices (its end points). Therefore the sum of the degrees of each of the vertices is twice the number of edges i.e. is even.

If there were an odd number of vertices with odd degrees then the sum of the degrees would be odd; thus there must be an even number of vertices with odd degrees.