Exploring Graph Puzzles with Maple Learn

Maple Learn

When I was in middle school, I was really into puzzles.  At one point I attempted the Three Utilities Problem.  This famous problem is deceptively simple: three houses and three “utilities” (heating, water, and electricity) are represented by dots on a flat piece of paper.  The goal is to connect each house to the three utilities without crossing any lines.

Figure 1: A starting setup.

I spent hours drawing lines.  I eventually looked it up online, and the internet told me that the problem was impossible.  I didn’t believe it, and tried for several more hours until I was forced to accept its impossibility.  I still remember this intense stint of puzzling to this day.

Figure 2: Cue twelve-year-old me saying “I’ll get it eventually…”

Looking back, I wonder if this sparked my interest in graph theory.  I know now that the Three Utilities Problem is truly unsolvable.  I know that the graph’s formal name is K3,3 and I know a full graph theory proof explaining its nonplanarity.  Nevertheless, I still love this puzzle, and I’ve recently recreated it in Maple Learn.

To do this, I created a table of x and y values and plotted all of them using the Point() command.  This allows the points to be fully click-and-drag-able.  Line segments joining two points automatically move with the points as well.  We then have a fully interactive graph directly in the Maple Learn plot window.  I can move the “houses” and “utilities” around all I want to try and solve the unsolvable.  I can also create other graphs to further explore planarity, paths, matchings, or any other aspects of the wide world of graph theory.

If you want to check out the document for yourself, it can be found here

﻿