## Embroidered Math

• Lesson
9-12
1

In this lesson, students are introduced to basic graph theory and Euler circuits. They stitch paths and circuits to create their own graphs. Students also problem solve as they design a route that creates the same pattern on the front and back of a canvas.

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.

 Graph Theory Activity Sheet

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.

Assessments

1. Have students draw a graph without an Euler circuit and explain why it does not have an Euler circuit.
2. Pass out a sketch of the Koenigsberg bridge problem, a famous problem where seven bridges connect the banks of a river with two islands in the river. Have students represent it as a graph and explain why it has no solution.
3. Ask students to write a journal entry explaining how the needlework contributed to their understanding of the graphs.

Extensions

1. Research applications of Euler graphs, such as the Chinese Postman Problem, which involves finding the most efficient way for a postman to traverse every street in a neighborhood.
2. Research Hamiltonian graphs, which are graphs that pass through every vertex exactly once, without restrictions on how many times an edge is traversed. One example that students may consider is the Traveling Salesman Problem, where a salesman wants to travel the shortest distance while visiting each customer on his route. Note that Euler graphs focus on traversing every edge, while Hamiltonian graphs focus on visiting every vertex.
3. Research isomorphic graphs, which are graphs where corresponding vertices are connected to corresponding edges. Also consider planar graphs, which are isomorphic to a graph where none of the edges appear to intersect.

Questions for Students

1. What conditions describe a graph that has an Euler path?

[No more than two vertices may have an odd degree.]

2. What conditions describe a graph that has an Euler circuit?

[All vertices must have an even degree.]

3. Why does the double-sided needlework always have an Euler circuit?

[Every time the needle enters the fabric, or paper, it must also come out. Therefore, every vertex must have an even degree.]

4. In the overhead examples, the circuit is completed by alternating stitches on the top and bottom and then turning back and reversing the procedure. When can a circuit be stitched continuously, without changing directions?

[The original pattern must have an odd number of stitches.]

Teacher Reflection

• Did the needlework enhance student understanding of the graph concepts?
• Were you able to use the needlework tasks to differentiate instruction among your students?
• Were concepts presented too abstractly? too concretely? How would you change them?
• Were students able to come up with potential applications for edge/vertex graphs?

### Learning Objectives

Students will:

• Define and draw vertex/edge graphs
• Describe Euler paths and Euler circuits
• Determine whether or not graphs have Euler paths and circuits
• Sketch graphs that have Euler paths and circuits
• Stitch the Euler circuit, considering the stitches on each side of the fabric to be distinct edges

### Common Core State Standards – Practice

• CCSS.Math.Practice.MP5
Use appropriate tools strategically.
• CCSS.Math.Practice.MP7
Look for and make use of structure.