MHB Prove Every Room w/ Odd Doors in House Has a TV Set - H for American Buyer

[Chris11]

Let H be a house with only one entrence. Assume that between any two rooms in the house there can only be at most one door. The owner's of this house, keen on selling to an American buyer, decide to place a TV set in every room with an odd number of doors.

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

 

[Sudharaka]

Let H be a house with only one entrence. Assume that between any two rooms in the house there can only be at most one door. The owner's of this house, keen on selling to an American buyer, decide to place a TV set in every room with an odd number of doors.

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

Hi Chris11, :)

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.

 

[Chris11]

Yep! That was my solution.