1

I came across this problem on this website, even though it was fun to answer it there was something sad I realized, and I wanted to ask this from the Math Stack Exchange community.

The question:

Connecting three houses to three utilities

To me honestly this question has no value. Just think about it "What is so important about this question we don't live in a 2D world, and there is no real life problem restricting us to act like living in a 2D world. So why bother connecting such things in this way? Don't get me wrong, Mathematics has wonderful application. Most of the problems actually has a real world use. But there are some exceptions "like this problem", why would anyone care to write proofs for this. And it's very sad for me when I see there are many useful questions that go unanswered on this website, why do people write long paragraph answers, and why does this question has so many upvotes. I honestly think there are more problems that deserve upvotes. Anyway everyone has the right to use his/her time and votes.

The point is this :

Does the three utility problem have any applications in real life? Will solving it or disapproving it push the human race forward?

Community
  • 1
  • So because we don't live in a 2D world, you think all planar geometry (and topology, which is what that problem is about) is irrelevant? "Will solving it or disapproving it push the human race forward?" -- No, because it's already well understood. But it might push students forward. – Jim Balter Jun 13 '17 at 09:25

3 Answers3

1

This problem in itself almost certainly has no applications. But it is a simple example in the topic of planar and non-planar graphs. If you Google "planar graphs applications" you will find lots of material to help with your query.

David
  • 82,662
  • 2
    Sometimes planarity is important. For example, when we are designing an integrated circuit. – André Nicolas Oct 16 '14 at 05:10
  • @AndréNicolas , oh I see. Thank you very much. –  Oct 16 '14 at 05:28
  • @AndréNicolas: Contemporary ICs have many layers (6+), things like 'congestion' ('density' of wiring), timing (signal propagation between clock cycles) and power are limiting factors at present. (Even PCBs have multiple layers nowadays.) – copper.hat Oct 16 '14 at 05:28
  • @copper.hat: Thanks, I am (as in other things) out of date. – André Nicolas Oct 16 '14 at 05:51
  • @AndréNicolas: I am currently refreshing my somewhat dated knowledge as I am considering gainful employment in the place & route area, in which my current depth is limited. (Lots of interesting numerical problems.) – copper.hat Oct 16 '14 at 06:03
  • It's not just a simple example of a nonplanar graph; it's a part of (almost) every nonplanar graph. Every nonplanar graph "contains" (in a sense that can be made quite precise) the utility graph or the complete 5-graph (or both), and there's a well-defined sense in which much the more common obstruction to planarity is the utility graph. – Gerry Myerson Oct 16 '14 at 06:28
  • Thanks @Gerry, I wasn't aware of the last part of that. Is it possible to briefly elaborate on how $K_{3,3}$ is more common? – David Oct 16 '14 at 06:30
  • It's something I read a long time ago. I'll try to track it down, but this could take a while.... – Gerry Myerson Oct 16 '14 at 06:32
  • On page 39 of Tucker, Applied combinatorics (3rd ed., Willey, 1995), it says, "Most nonplanar graphs contain a $K_{3,3}$ configuration. $K_5$ configurations are less common." But there is no attempt to justify the statement. – Gerry Myerson Oct 16 '14 at 12:18
  • I think I found the place where I first read it. Trudeau, Dots and Lines, page 86: "The vast majority of nonplanar graphs contain an expansion of UG...." But I don't see any justification of this anywhere in the book. – Gerry Myerson Oct 16 '14 at 22:41
  • Thanks @Gerry. Sorry to have given you all that work for little in the way of concrete results! – David Oct 16 '14 at 23:12
1

With due deference to you (this is not intended as a slight on your question) and to @AndreNicolas and noting that I am an engineer who is extremely interested in real-world application.

Consider:

Does the Mona Lisa have any applications in real life? Will painting it or not painting it push the human race forward?

Mona Lisa

Humanity has two choices:

  • The Sir Edmund Hillary choice

Nobody climbs mountains for scientific reasons. Science is used to raise money for the expeditions, but you really climb for the hell of it.

  • or the Willie Sutton choice:

I rob banks because that’s where the money is.

Dale M
  • 2,813
0

Well, the resulting graph is K(3,3), and there is a theorem which states that a graph is not planar if and only if it contains a graph which is K(3,3) or K(5) (a pentagon with all diagonals drawn).

What's the importance of knowing if a graph is planar or not? for a while an integrated circuit had to be planar, for example.

And besides all of this, the original problem is fun because you may devise many creative answers to overcome the impossibility :-)

mau
  • 9,774