Ask, "When I say graph, what do you think of?" [Expected answers include coordinate graphs, bar graphs, pie graphs, data collections, grids, slope-intercept.] Show the Graph Theory overhead. Tell students that in graph theory, a graph is a collection of points, called vertices, and the edges that connect them. Note that edges do not have to be straight; the only requirement is that they have vertices as their endpoints. Mention that multiple edges can connect the same two vertices and an edge can connect a vertex to itself.
Discuss how a graph on paper can be a model of a real-world situation. For example, the vertices of a graph might represent houses, and the edges might represent streets. Ask students for other situations that might be modeled by graphs. [Airports and routes, cell phone signals and towers, assignment of class sections to rooms.]
Pass out the Graph Theory activity sheet. Explain that graphs can be used to find the most efficient way to carry out a task. For example, a road striper (the machine that paints lines down the middle of a road) or a street cleaner might want to travel along each street in a town exactly once. By drawing a graph that includes streets as edges and intersections as vertices, the driver can use a graph to determine the optimal path for the job. A path that starts at a vertex and traces each edge exactly once is called an Euler path, named after the mathematician Leonhard Euler (pronounced oil‑er). An Euler path that starts and ends at the same vertex is called an Euler circuit.
Have students trace paths on the graphs and decide if each graph has an Euler path or circuit. Then, students should draw their own paths. Encourage students to look for patterns and try to draw a conclusion about what graph features make it possible to trace an Euler path or circuit. If students are not ready to draw a conclusion, they will be able to return to the activity sheet later in the lesson.
Needlework
Distribute dot paper to each student. Have students draw an Euler circuit on the dot paper, using the dots as vertices. Distribute sewing needles and thread to each student. Explain that they are going to use stitches to trace their circuits. Help students thread their needles, if necessary. Then, tape the loose end of the thread to the back of the paper near the starting point. Have students push the needle through the starting point and then make a stitch by pushing the needle through at the next vertex and repeating until all edges have been traced, either on the front or the back of the paper. Students can use their stitching to verify that they have not traced any edges more than once. Below are some examples of circuits that have been stitched.
Blackwork
Have students look at the front and the back of the dot paper on which they stitched their designs. They should note that the design is different on the front and the back. Blackwork embroidery creates the same image on the front and back sides of the canvas. Remind students that their canvas is dot paper. Show students Blackwork 1 overhead. Explain that they are going to trace a path that, when stitched, creates the same image on the front and the back. You will track whether the stitches are on the front or the back of the paper by recording it in the appropriate column. Note that stitches alternate between front and back, depending on where the needle begins. The beginning and ending vertex for each stitch is recorded in parentheses. The first letter is where the stitch begins, and the second letter is where it ends. When the stitches are listed in order, the ending vertex of one stitch should be the same as the beginning vertex of the next stitch. While analyzing the stitches listed, trace them on the graph above, using different colors for front and back stitches. In the end, each edge will have be been traced in two colors, indicating that the image would be the same on the front and the back of the canvas. Students may also want to draw this pattern on their own dot paper and stitch the pattern to see better how it works.
Show the Blackwork 2 overhead. Explain that some designs are much more complicated and require many more stitches. In these designs, the stitches are numbered. The T indicates that the stitch is made on the first trip around the pattern, and a B indicates that it is made on the return trip. As you trace the stitches, again use two colors to indicate the stitches on the front or the back. Have students help you problem solve about where to begin each stitch so that the back image will look identical to the front image. Again, when you are finished, each edge should be traced in two colors.
Show the Blackwork 3 overhead. Again, the numbered stitches can be traced in two colors, with color designating whether the stitch is on the front or the back of the canvas. The T stitches are made between the starting point and the turn around, and the B stitches are made after the turn around and on the way to the finish. Ask students why they think this design is called "Journey and Side Trips." Discuss the efficiency of the stitching pattern; there are very few stitches required between the turn around and the finish.
Wrap-Up
Since we actually stitch on both sides of the canvas, every edge on the front will have a matching edge on the back. Explain that the degree of a vertex is the number of edges that connect to it. Ask, "Why will every vertex have an even degree?" [Each time an edge passes through the front, there is also one on the back. The total degree will always be a multiple of two.] Have students return to the Graph Theory Answer Sheet and complete the last two questions.
