August 4, 2005

The class began with a discussion about nodes and edges in a graph. Bobby explained to the students how all points with lines connecting them were called nodes and all lines in between nodes were called edges. Next, she explained the definition of a complete graph: a graph is complete if every node has as many lines going out of it as the total number of nodes-1. She then had four students make a complete graph using themselves as nodes and ropes as edges. When they had done this, forming a square with two diagonal lines across it, she told them to make their graph in such a way that no lines crossed.

Once they had figured this out Bobby explained how a matrix could be used to demonstrate a graph. She then gave them a problem in which there were three houses and three stores, and every house needs to get a path to every store without crossing any other paths. The trick, though, was that the problem was impossible!

The next activity involved drawing letters of the alphabet without lifting the pencil and without repeating a line. They worked through the whole alphabet determining which letters could be drawn this way. Using Excel the students constructed graphs of the number of edges coming out of nodes in different letters. They discovered a pattern that showed them all letters with two or less odd nodes could be written this way.

To test this discovery Bobby gave them a problem that involved bridges in a garden. She asked them to decide if it was possible to traverse all the paths without crossing the same path twice. By converting the problem into a graph the class was able to see that there were more than two odd nodes, so it was impossible.