Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicate:
3 Utilities | 3 Houses puzzle?

A man has built three houses. Nearby there are gas water and electric plants. The man wishes to connect all three houses to each of the gas, water and electricity supplies.

Unfortunately the pipes and cables must not cross each other. How would you connect each of the 3 houses to each of the gas, water and electricity supplies

My concern is: If pipes and wire cannot cross with house and stations, then how to prove a solution does not exist by graph theory or combinatorics?

link to the original problem:

share|cite|improve this question

marked as duplicate by Mike Spivey, 5PM, Davide Giraudo, draks ..., Hagen von Eitzen Jan 19 '13 at 22:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

The short graph theory proof is: The graph $K_{3,3}$ is not planar. – Hagen von Eitzen Jan 19 '13 at 16:28
@HagenvonEitzen - What is planar and how to prove that it is not planar? – Victor Jan 19 '13 at 16:36
I made use of a theorem of Kuratowski, which is admittedly not a trivial result. – Hagen von Eitzen Jan 19 '13 at 18:05
up vote 1 down vote accepted

I think i got the problem now: A combinatoric/graph proof could be given by the Euler's formula:

V - E + F = C+ 1

share|cite|improve this answer
6 vertices, 9 edges, one connected component, hence 5 faces. Why can there not be 5 faces? – Hagen von Eitzen Jan 19 '13 at 18:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.