What are the 3 utilities?
In the earliest publication found by Kullman, Henry Dudeney (1917) names it “water, gas, and electricity”. However, Dudeney states that the problem is “as old as the hills… much older than electric lighting, or even gas”. Dudeney also published the same puzzle previously, in The Strand Magazine in 1913.
Is the gas water electricity puzzle possible?
The puzzle is not solvable. Would you want someone else’s water, gas, or electric line running through your house?
What is the 3 utilities problem describe it?
The utility problem posits three houses and three utility companies–say, gas, electric, and water–and asks if each utility can be connected to each house without having any of the gas/water/electric lines/pipes pass over any other.
Is the 3 utilities problem possible?
In the most conventional sense – on an ordinary, two-dimensional sheet of paper, as an example of a planar graph – it’s not possible to solve the three utilities problem. Inconvenient though it may be, not all of those houses can receive their connections.
What is a K5 graph?
K5 is a nonplanar graph with the smallest number of vertices, and K3,3 is the nonplanar graph with smallest number of edges. Thus both are the simplest nonplanar graphs.
Why is the three utilities problem Impossible?
The problem states that the graph must have 9 edges- 3 from each of the houses to a utility. Since the most efficient method of creating 5 faces on the graph results in 10 edges, this problem is impossible to solve.
What is a K3 3 graph?
The graph K3,3 is called the utility graph. This usage comes from a standard mathematical puzzle in which three utilities must each be connected to three buildings; it is impossible to solve without crossings due to the nonplanarity of K3,3.
Is K5 a eulerian?
(a) The degree of each vertex in K5 is 4, and so K5 is Eulerian. Therefore it can be sketched without lifting your pen from the paper, and without retracing any edges. (b) (i) In Kn the degree of each vertex is n − 1. A graph is Eulerian if and only if the degree of each vertex is even.