Author:
Anthony Beckwith
Mathematics Department Chair, Concord-Carlisle Regional High School

With:
Tim Moschini
Concord-Carlisle Regional High School, Class of 2001

Concord, MA
April 23, 2001

A Mathematical Exploration
I believe that one of the most exciting things that can happen in a mathematics class is to find a problem that, for whatever reason, grabs a student's interest to the point where the student begins asking and answering new questions related to it, follows the problem wherever it leads, and wants to hold on to the problem until they have it solved. The work involved comes that much closer to "doing real mathematics" when the problem itself arises out of curiosity, is open-ended and, therefore, has not been solved before by scores of previous students, and the path to solving the problem is determined entirely by the solver.

I had just such an experience with one of my students this year in my Advanced Topics in Mathematics class at Concord-Carlisle High School. What follows is both the story of how this student and I collaborated on a problem that we could not let go of as well as a description of the specific mathematics that grew out of that collaboration.

Enter Topology
Advanced Topics in Mathematics is a course for seniors who have taken Pre-Calculus as juniors but are not ready to take Calculus in high school. This mixed ability-level course is designed specifically to try to get students engaged in mathematics and to see the world of mathematics from different perspectives. The topics covered this year included Number Theory, the mathematics of the Global Positioning System, Fractal Geometry, Chaos Theory, Topology, and Web Design. I introduced the field of Topology as the "study of properties of figures that remain unchanged upon deformation" and I told the students that two figures are "topologically equivalent" to each other if one can stretch, shrink, or generally deform (without cutting, attaching, or folding) one figure into another. In Topology, measurement of length, angle, and size are irrelevant; connectedness and other related properties are studied instead. In Figure 0. below, the shape on the right is topologically equivalent to the shape on the left. The fact that one is oval-shaped, while the other is a 7-sided polygon, is irrelevant. A topologist would look at what properties they share rather than what properties make them different; in this case they are each essentially non-intersecting closed curves.


In a similar fashion, one might draw a diagram of a route from one location to the other, without attempting to maintain the scale or the size or shape of the locations or the specific angles at which the route twists and turns. The important property of the diagram would be the connectedness of the various points along the route, not the lengths or angles involved.

We looked at many 2-dimensional and 3-dimensional shapes from a topological viewpoint, watched a video on the "shape of space", and got a feel for what it means for 2 objects to be topologically equivalent to each other. We then spent a significant amount of time working with ideas from Network Theory (or "Graph Theory"). After looking at several examples of problems that led to "networks", I gave the definition of a network as "a diagram representing a real-world situation using only vertices (points) and edges (line segments)." I defined the degree of a vertex as the number of edges emanating from it and a "tree" as being "a connected network with no circuits (or 'closed loops')". In Figure 1 below, all three diagrams are networks. More specifically, (a) is a connected network; (b) is a disconnected network; (c) is a tree:

We also did some work with Euler's Formula, relating the vertices, edges and faces of any network (V+F=E+2), and Kruskal's Algorithm, using it to find the minimum spanning tree (least expensive way to connect all vertices) for a weighted network. This particular year, I spent more class time than usual talking about the variety of types of trees and their applications to the real world. We looked at how minimum spanning trees are used to find the most cost-efficient telephone, internet, mail-delivery, etc. connections between a number of locations. The study of networks also arose in analyses of galaxy clusters, maps of the growth of spores, the design circuit boards, and decision-making analyses.

Trees
Students were given a variety of assignments, including one that had them list all of the topologically distinct trees with a given number of edges. Figure 1.5 represents an example of 3 trees that are all topologically equivalent to each other (with the 3rd being the clearest representation):

We first generated a list of all the topologically distinct trees with 1, 2, 3, and 4 edges (see Figure 2.)

We put this information into a table to try to determine if there was a pattern to the numbers:

Edges	# of Trees
1	1
2	1
3	2
4	3

One student noticed that the sequence of the number of trees appeared to be the same as the well-known Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, 21,...). However, when the students worked out the 5-edge trees, the total turned out to be 6 (see Figure 3 below).

I then gave the students a list of the numbers of trees for up to 12 edges and we discussed how mathematicians would want to find a formula to predict the number of trees (n), given any number of edges (e).

e	n
1	1
2	1
3	2
4	3
5	6
6	11
7	23
8	47
9	106
10	235
11	551
12	###

Another student noticed that there might be a pattern to n, found by adding previous numbers together. For example, for e = 3, n = 2 = 1+1 (the two previous numbers in the list) and for e = 4, n = 3 = 2+1.

e = 5	n = 6 = 3 + 2 + 1 + 1
e = 6	n = 11 = 6 + 3 + 2
e = 7	n = 23 = 11 + 6 + 3 + 2 + 1
e = 8	n = 47 = 23 + 11 + 6 + 3 + 2 + 1 + 1
e = 9	n = 106.....doesn't work!!!

Although neither conjecture proved to be true, I was encouraged that the students were beginning to think and make conjectures. For them, this was out of the ordinary for a math class, where they would normally solve problems that have only one correct answer and where that answer was predetermined. The students in the Advanced Topics in Mathematics classes are generally those who either have not had much success in mathematics or have not found it interesting or engaging enough to put time, thought, or energy into it. Making conjectures and testing them for validity were the first steps in approaching mathematics from a fresh perspective.


Irreducible Trees
We then extended our discussion of trees to include "binary trees", "rooted trees", "planted trees", and "series-reduced trees". I gave the definition of "series-reduced" trees, (also called "irreducible trees") as trees containing no vertex of degree 2. After working out a couple of irreducible trees, I asked the class to think about why these kinds of trees might have been given the name "irreducible". What we came up with was that a vertex of degree 2 can be seen, in some ways, as a "redundant" vertex. If one were to trace a path through the tree, a degree-two vertex would not allow for any alternative choice of paths. In a sense, the edge just "passes through" the vertex. In Figure 4 below, the tree on the left can be thought of as "reducible" in the sense that the middle vertex could be removed without really affecting any path through the tree. In the diagram on the right, no vertex can be removed without removing an endpoint or rendering the tree "disconnected", thereby making it no longer a tree.

In class, I had the students try to list all the possible irreducible trees with a given number of edges. They gradually made their way up through the 8-edge irreducible trees (see Figure 5.).

This is summarized by:

e	n
1	1
2	0
3	1
4	1
5	2
6	2
7	4
8	5

...continued...