August 2024
Welcome to EFM's August Newsletter!
It is essential that every caregiver in the world reads books and does math with their young children!
EFM believes in every child’s mathematical right to equity, opportunity, and personal fulfillment.
News
Professional Development – A large school district in Canada contacted EFM about doing PD presentations. If an EFM PD is of interest to you, let’s set something up! Generally speaking, if you are willing to pay travel expenses and give feedback on EFM materials, I am happy to come to your district and do presentations and workshops. I have two topics all set to go: one on playful learning in the classroom and at home, and a second on problem exploration in the classroom.
Donations – EFM donations come in all sizes and sources. We’ve people give us $10 to $5000, and we’ve had employees have their employers give us $200 and $250. Make an EFM donation and help improve early math education!
Puzzle Playing Cards – We have a large inventory of grades K-3 and 2-5 puzzle playing cards in English and Spanish. The cost is just $3 per deck, and we are happy to discuss grants for schools. Please go to our ordering page if you are interested in them.
App for Beginning Early Math Teachers - In addition to EFM's mobile app for families, EFM would like to develop a free mobile app for educators. This new app would be aimed at beginning early math teachers around the world who have minimal training and resources. We hope to adapt our current large set of materials to make them useful in this context. However, we need some guidance on what these should look like in the US (perhaps some Head Start regions) and in other worldwide communities. Please contact me if you would like to collaborate on this project.
Graph Theory for Preschoolers
In the last two newsletters I talked about ways you and your child could play with Topology. This month I’d like to dip into the topic of Graph Theory. The graphs I’m talking about are not the ones used to represent data for data analysis – we will look at those in an upcoming newsletter.
These graphs consist of points, referred to as nodes, some pairs of which are connected by lines, referred to as edges. A node’s degree is the number of edges that attach to it. A planar graph is one that can be drawn on a piece of paper without any of its edges crossing each other. Graphs are sometimes abstract things, which are fun to play with in their own right, and sometimes they are a way of understanding and analyzing a physical situation without getting distracted by useless information. Here is an example of such a graph.
The topic of Graph Theory does not lend itself to multi-player games, with one exception – two months ago in the June newsletter I covered the game of Sprouts, which is a 2-player game involving planar graphs. However, Graph Theory has lots of fun puzzles, many of which I will present today.
The first puzzle is the most famous, and it is often cited as the beginning of Graph Theory and the field of topology. Analyzing this puzzle demonstrates the strength of taking a situation and representing it as an abstract graph.
The Seven Bridges of Königsberg
The story goes that the people of Königsberg were proud of their seven bridges and wanted to have a parade that crossed each of their bridges exactly once. No one could think of a way to do it. Here is that puzzle as described on one of EFM’s puzzle playing cards.
I also mentioned this puzzle in my March, 2023, newsletter. There the emphasis was on taking math situations and wrapping them inside good stories to make them engaging. Leonhard Euler helped establish Graph Theory by giving a talk on this puzzle in 1735.
In this problem, the actual distances and shapes of things are unimportant. The heart of this problem is modeled as a simple graph, where each land area is a node and each of the seven bridges is an edge.
Yes, the puzzle is impossible, but Why? Unearthing The Why is the fun part. To explore that, use one of the most important problem solving strategies: Learn from simpler versions of the problem and do lots of examples. Emphasize the usefulness of this strategy to your child, and see if they can make their own examples. Here are a few, but there are many more. Try to make parade routes on each example, and gather observations about where the parades must start and stop, and whether they are possible at all. What patterns can you find and what conjectures can you make?
5-Room puzzle – Line Crossing Problems
There are a lot of line crossing puzzles out there. This is perhaps the most popular one of this type. The challenge is to draw one continuous line that crosses all the edges in this diagram exactly once. The following example shows a path that does not work.
Model this as a graph where the nodes are the insides of the rectangles plus one more node for the entire outside region, and the edges represent going across each of the individual sides in the diagram. While the graph is a bit complicated (not my best artwork), if you apply what you learned about the Bridges of Königsberg puzzle to this graph, you will find it very easy to analyze.
Paths on Graphs
These first two puzzles are examples of the challenges of finding paths in graphs. Mathematicians love to define things and give names to them, and this is no exception. A path that traverses every edge of a graph exactly once is called an Eulerian Path, If the path also begins and ends at the same point, it is called an Eulerian circuit.
As Euler and others have studied, and as you may have just analyzed in the last two puzzles, the key to being able to find Eulerian paths and circuits is counting the number of nodes that have odd degree.
You can make pretty graphs and challenge each other to find a Eulerian path. It helps a lot to know where to begin and end your path. Give this one a try:
A Hamiltonian path is one that visits every node exactly once. If the path begins and ends at the same place, it is called a Hamiltonian circuit.
In general, unlike Eulerian paths, it is not so easy to tell whether a Hamiltonian path will exist for a given graph.
The Knight’s tour is a puzzle that is an example of such a challenge. Suppose you have a chess knight positioned on one of the squares of an n x m chessboard. Is it possible for the knight to visit every square of the chessboard exactly once? Can it return to where it started at the end? You can turn this into a Hamiltonian Path problem by creating a graph whose nodes represent the squares on the board and it has an edge between two nodes if there is a knight move that goes between them.
A classical Hamiltonian path problem is the Traveling Salesperson Problem (TSP). Suppose someone wants to visit all the cities on a sales route, and suppose further that the edges connecting some of the cities show the travel times (or distances or cost) between the cities. How do you find a Hamiltonian Circuit that minimizes the total travel time (or distance or cost)? Delivery trucks deal with a version of this problem every day.
In these two graphs, each edge is labeled with a “cost” for traveling on that edge. The TSP challenge is to find a Hamiltonian circuit with the smallest possible total cost. You and your child can make maps for each other and challenge the other person to find a best possible circuit on the map. Use numbers and map sizes appropriate for your child’s skill level.
Handshakes and Acquaintances
Suppose there are 8 people at a party and some handshaking takes place. EFM has several Puzzles of the Week that talk about this situation. Model this by using 8 nodes, one for each person. Make an edge between two people if they shake hands. You can use this same kind of model where the edges might represent people who know each other, or perhaps people who are related.
In the handshake model, the degree of each node, which is the count of its edges, is the number of people that person shook hands with (including the possibility of 0 handshakes for a disconnected node). One of our puzzles asks if it is possible for all of these degrees to be different.
There are many questions one can ask about which sets of degrees are possible. Is it possible for all the degrees to be even or all odd? One interesting fact about all graphs is that the sum of all the degrees in a graph is twice the number of edges (Why?). So, in our handshake problem, there must always be an even number of people who make an odd number of handshakes. What other restrictions are there?
Suppose you have a graph of all the people in the world, where two people are connected if they know each other. Can you get from any node to any other node in this graph, or does it break apart into separate graphs? For a connected portion of this graph, what is the most number of edges you must travel on to get between any two people? This is sometimes called the degree of separation between two people. This idea has been applied to actors who have been in films together, and it assigns to each actor a Kevin Bacon Number.
Family Trees
In graph theory, a tree is a connected graph that has no cycles in it. Equivalently, there is exactly one path between any two nodes. You can make a graph out of family relationships by connecting two people if one is a descendant of the other. These are often called family trees.
You can explore with your child what would happen if a family tree was truly a tree in the graph theory sense. If it were, how many people would there be at each level? Notice that the number of people doubles with each level (using biological relationships). Starting with one person, the size of the generations would be 1, 2, 4, 8, 16, and so on. Ten generations back would be 1024 people. Twenty generations back would be 1024 x 1024 people. By forty generations, you would have more people than have ever existed. Can your child figure out what went wrong?
Graph coloring
Just as you can study coloring maps, for a given graph you can ask what is the minimum number of colors you need to color its nodes so that no edge has the same color on both ends. This is called the chromatic number for the graph.
There is a direct connection between flat maps and planar graphs – let the nodes of the graph refer to the regions of the map, and let there be an edge in the graph whenever two regions share a border. The four-color theorem says that any flat map needs at most four colors, and this result carries over to planar graphs – the chromatic number for any planar graph is four or less. Draw a few planar graphs and try coloring them with your child and check out the result!
Wrapping Up This was a whirlwind tour of topics and beginning puzzles of Graph Theory. Of course I had to leave a lot out. I hope you and your child found some engaging nuggets among all these puzzles. Next month I will continue this tour of advanced math topics that can be made simple, engaging, and fun for young children.
If you have any questions or comments, please send them our way! We would enjoy the opportunity to chat with you. Also, if you are interested in collaborating with us or supporting us in any fashion, we would love to talk with you about ways we can work together!
August 18, 2024
Chris Wright
Chris@EarlyFamilyMath.org
Twitter | Facebook | Instagram
Early Family Math is a California 501(c)(3) nonprofit corporation, #87-4441486.