Movement in Intro to Graph Theory

Targeted: Middle School

Why Graph Theory?

Teaches basic concepts of a higher level math topic, which can encourage kids to go into higher education.

Does NOT align with state standards, meant to be lessons for summer programs, after school activities, or an extension.

Activities/Concepts

Gale-Shapley Algorithm

Coloring

Handshaking Lemma

1

Goals

Odd Cycle Coloring

2

4

3

Even Cycle Coloring

Handshaking Lemma

Gale-Shapley Algorithm

The smallest possible coloring is 3

The smallest possible coloring is 2

Σdeg(V)=2*E

There are two possible matchings

Assessment

Close each activity with a discussion, making sure key takeaways are stated

Homework to see if they can translate what they physically did onto paper

During Class

After Class

Materials

Object to represent coloring:

• Jersey
• Holding marker
• Construction paper

• Paper/Poster Board

​

Optional:

• Additional Staff
• Name Tags

Object to represent matching:

• Flowers
• Rings
• Chips

All Activities

Gale-Shapley Algorithm

Coloring Cycle

Handshaking

1

Coloring

2

Gale-Shapley

3