Graphs
What comes to mind when you read the word “graph”? Graph paper? Graphing calculator? High school math homework?
Unfortunately, the word is overloaded with meaning, and none of the above are what a mathematician usually means when they say “a graph." They mean something like this.
More formally, a collection of nodes or vertices (circles) and edges (lines connecting circles).
Graphs and Graph Theory—the field studying them—are extremely important because so many things can be modeled as a graph. Our lives are better today due to math and applied math work on graphs!
For example: GPS routing. Transport networks such as roads can be modeled as a graph. The edges are streets, the vertices are intersections. Edges can have a weight or cost associated with them, such as the distance of a road, or estimated traffic time. Routing software finds the fastest route by finding the “minimum cost” (read: shortest distance or lowest traffic time) path from you to where you’re going. (Advanced reading on how this path is found: Dijkstra's Algorithm)
Graphs are easy to introduce as a concept with kids because they’re so fun to draw. I started drawing graphs with my daughter when she was still 2. I think early introduction is worth it: at worst, they have a vague familiarity with the name and concept later. At best, you spark excitement and interest!
Activities for 2 to 4 year-olds
Find the path from you to me
The first activity I started with was just drawing a simple graph with an Asher character on one node and Dad character on another and giving a challenge: draw a path from Asher to dad. Here’s a picture of something we actually did when she was 2.
Asher found this very fun. It helps to have a variety of colors to distinguish the paths.
Modify the game: make the graph more complex, count the number of paths, find the path that takes the least edges, find the path that takes the most edges.
Bridges of Königsberg
In the 1700’s, the city of Königsberg had two islands connected to the surrounding land mass by seven bridges.
The people of Königsberg had a question: is it possible to take a walk and cross all seven bridges, without crossing any of them twice? A famous mathematician, Leonhard Euler, worked on this problem in 1736 and his work is considered to have essentially invented graph theory. Why? His solution relied on describing the land and bridges as something like a graph
I’ll mention more advanced exercises with this problem later, but for young kids, draw this out and use colored pencil to try to find a path. Or better yet, use blankets for land and blocks for bridges and try to walk it yourself.
Numberphile is a great math YouTube channel. Watch their video on the problem and its solution.
Activities for 5 to 8 year-olds
Coloring
There’s a whole subset of graph theory problems called coloring problems. In general, the challenge is something like: given N colors, find a way to color the vertices of a graph such that no vertices of the same color share an edge.
For example, given only two colors, it would be impossible to color this graph so that no connected vertices have the same color
Of course, it would be possible with three colors.
And, if we remove an edge, you could do it with two colors.
An analogous problem is coloring maps, or just touching shapes. How many colors would you need to color the shapes below, such that no two shapes have the same color?
Make a game of this: take turns drawing overlapping shapes like the above. Try to guess before coloring how many colors you’ll need. Challenge each other by limiting how many colors can be used.
Something that’s very interesting is that any set of overlapping shapes can be colored to satisfy the rule with four colors. This is called the Four Color Theorem. It seems crazy, but try it! Make a game of this, too. Tell your kids: draw as crazy of shapes as you can; I’ll color it using only four colors, and no shapes of the same color will touch.
This also applies to coloring the vertices of graphs, so you can try it that way, too. The only catch is that it must be a planar graph, meaning no edges are allowed to cross. If edges could cross, the following graph would need five colors to satisfy that no vertices of the same color share an edge.
Remove the crossing edge, and it works with four colors.
Why are drawn shapes like graphs with no crossing edges 🤔
These coloring problems might seem like just a mental puzzle or brain teaser, but they have lots of applications. A lot of abstract math is like that. For example, exam scheduling: suppose we want to schedule exams for students and ensure no student has two exams at the same time, what’s the minimum number of exam slots needed? This problem can be modeled as coloring a graph: every class is a vertex, every student is an edge. If two connected vertices have the same color, it means a student will have an exam conflict. The minimum number of colors needed to satisfy the no-touching rule will be the minimum number of exam slots needed. See more applications here.
Graph your map
As mentioned in the introduction, your learner might be interested to know that the app on your phone giving you directions understands the world of roads as a graph: vertices are intersections, edges are roads. Draw a graph representing the roads in your neighborhood, or the roads to a favorite place.
Draw the path through the graph that you usually drive. Use different colors to draw other graphs. Wonder at how the app on the phone might find the best path.
Activities for 9 and Up
Advanced Bridges of Königsberg
(See Activity 2 in the Activities for 2 to 4 year-olds section for context)
Watch the Numberphile video by yourself beforehand to make sure you understand the problem well.
With your learner, first try the simple problem: draw the map with the bridges. Can they find a path that crosses every bridge once and no bridge twice?
It’s not possible, but why? What would you have to change about the map to make it possible? What does this tell us about why it’s not possible?
These questions lead us towards the “general solution.” A lot of math is about finding a general solution, rather than a specific one. As discussed at the end of the video, that’s what Euler did with this problem. We’re interested in not just “it works with six bridges instead of 7,” but rather “it’s not possible if more than two vertices has an odd number of edges.” Or, in land and bridges terms: if more than two land masses has an odd number of bridges, it’s not possible. This is a general solution because it applies to every possible number of bridges and land masses.
See if your learner can find this general solution themselves, without watching the video. Euler worked on this problem by describing the land and bridges as a graph, so you might start there. Having only seen the map, try to draw a graph that would represent the map. Then modify the graph in different ways to make it possible. Are there commonalities in what works and what doesn’t?
Maybe try to simplify the problem first: start with two vertices and one edge (two land masses and one bridge), does that work? How about two vertices and two edges? Keep going. If you think you find a rule, try to prove it wrong. Don’t get discouraged or give away the solution too quickly. Maybe plan to watch the video a week or two after you first work on the problem.
Thanks for reading! This is my first newsletter, so let me know how I can improve. What do you like? What don’t you like? Shorter, longer, more of some detail, less of other, etc.
Wilson