- Thread starter
- #1

Prove that the the American will be able to find a TV set when he comes to evaluate the house.

- Thread starter Chris11
- Start date

- Thread starter
- #1

Prove that the the American will be able to find a TV set when he comes to evaluate the house.

- Feb 5, 2012

- 1,621

Hi Chris11,

Prove that the the American will be able to find a TV set when he comes to evaluate the house.

I think we can use the Handshaking lemma to solve this problem. Suppose every room in the house has even number of doors. Represent rooms by vertices and doors by edges and we get a finite graph (since the number of rooms should be finite). We shall consider the garden (outside) also as a vertex. The "garden vertex" has degree 1 (only one entrance), and all the other vertices have even degrees. According to the Handshaking lemma this cannot happen. Therefore there should be at least one vertex (a room) except the "garden vertex" with odd degree (odd number of doors). This room contains a TV and if the buyer walks into each room he should find this.

Kind Regards,

Sudharaka.

- Thread starter
- #3