This is a version of an article that was originally published in AIN Quarterly. For that journal, it was suggested that I take all the “maths” out. Here we go!
This is a story about a single moment. A moment where I forgot my improv knowledge, and remembered it before it was too late. A wonderful experience, continuing through today, that would not have happened had I not remembered. We all have our moments forgetting our AI knowledge. Sometimes we remember in time, sometimes we don’t. This is a story about one of mine when I remembered.
The Math(s) for the curious
Feel free to skip this part if you don’t like mathematics. The specific content is not the point of the story. Scroll down to “The Tale” to skip the math(s).
Think of a graph as a collection of facebook accounts. If two people are facebook friends, draw a line between them to indicate such. Here are three examples of graphs:
(5 facebook accounts)
(5 facebook accounts)
(8 facebook accounts)
Notice that Graph 3 has two different groups of people, with no friends between them. Those groups are called components, so Graph 3 has two components. Good? Good.
A graph is Eulerian if everyone has an even number of friends, and only one component. Graph 2 is Eulerian. Graph 1 is not, because there are people with odd numbers of friends, and Graph 3 is not, because it has two components.
A graph is Hamiltonian if you can start with one person, and make a happy cycle between all the accounts and wind up back where you started, without using any person more than once. (You may suspect that the little circles can stand for more than just facebook accounts – you would be right). Graph 2 is not Hamiltonian, because any such cycle would have to use the middle person more than once. Graph 3 is not Hamiltonian, because you can’t get from one component to the other.
Now let’s talk about toughness. A graph is tough if it is hard to break. Specifically, it means the graph is connected – has only one component. If any one account is deleted by Meta, the company that owns Facebook, then the result will still be connected! If any two accounts are deleted, the result can have at most two components, no more. If three accounts are deleted, the result can have at most three components, etc. Graph 1 is tough. If you delete any n accounts, the result will not have more than n pieces left. Graph 2 is not tough – if you delete the middle vertex, you will have two components. Graph 3 is not tough – it is not connected.
That’s all the math(s) that is (are) in this story.
I was teaching an international summer program for math-enthused students. We had spent a delightful few days talking about Eulerian graphs, Tough graphs, and Hamiltonian graphs. I came to the climax of this part of the course – I had the students get into groups and prove that IF a graph was Hamiltonian, then it was Tough.
As we were summing up our discussion, and I was mentally rehearsing the introduction to our next topic, one student, Harris Spungen, asked if the converse of my statement was true – if every Tough graph was a Hamiltonian graph.
I had anticipated that question, and smoothly put this graph on the board:
We verified that the Petersen graph was tough and that it was not Hamiltonian.
I was still on autopilot when Harris raised his hand, and told me he came up with a new conjecture:
I knew his conjecture had to be false, because if it were true, it would be in all the textbooks. So I said, “I don’t believe you are correct.” I thought for minute, trying to come up with a quick counter-example. If you’ve ever taught, you know how long a minute is when you are standing at the board, thinking. I couldn’t up with one, so I said “I’ll get back to you on this tomorrow,” and went back to my lecture plan.
I said “I’ll get back to you on this tomorrow,” and went back to my lecture plan.
I’d been teaching for close to 30 years, and won teaching awards at four different universities, and I said “I’ll get back to you on this tomorrow,” and went back to my lecture plan.
I’d been going around the country giving my successful “Improv for Educators” workshops, where one big lesson was how to roll with what is actually happening in front of you, and I said “I’ll get back to you on this tomorrow,” and went back to my lecture plan.
I was teaching an ungraded course where the syllabus was whatever I said it was, a course where I wanted the students to learn the thrill of mathematical discovery, a course in my favorite subject to think about, and I said “I’ll get back to you on this tomorrow,” and went back to my lecture plan.
Fortunately, I thought
“Wait! What am I doing!”
And then I said to my class, “Hey – you know what? Nothing else I had planned for today is as interesting as Harris’s conjecture. Let’s try to find a counter-example.”
The extroverted students were at the chalkboard immediately, drawing and arguing. I erased all my notes and pictures to give them room. The more introverted ones had notebooks out, sketching and experimenting, occasionally showing pictures to each other. Five minutes passed. Ten.
A few of the ones whose previous mathematical experiences all involved immediate success were getting frustrated and mentally checking out. And a couple of the ones who had confidence problems were also checking out.
But then one group of three boys at the board called out, “I think we got it.” I was in full on improv mode, and made myself look busy and distracted and asked the checked-out students for a favor – “Can you see if they are right?” And they were all too happy to be useful, running up to the picture, to see if it was a counterexample. It wasn’t – they showed it wasn’t. But by then someone else had a proposed counterexample, and off they went – the Harris Graph Verification Squad.
Fifteen minutes. Twenty. When the HGV squad were convinced that a counter example worked, a teaching assistant and I would take a look, dashing hopes to the ground. Everyone in the room was so excited. Had Harris come up with a new condition after all? Nobody knew, not even me. And that is another lesson from improvisation in education. Uncertainty is okay. Chaos is okay. There’s a joy in not knowing. Just like on stage, when neither the audience nor the actors know how our heroes will escape from the cave guarded by bears. The teacher didn’t know if Harris was right, the students didn’t know if Harris was right, and Harris was having the time of his life trying to prove himself wrong.
Thirty minutes. Ask a teacher friend how often you get a class of students completely involved in an activity for 30 minutes. Laughing, yelling, groups splitting and reforming. All looking for this holy grail, which in my mind I was calling a Harris Graph. While the HGV Squad ran from group to group, and the TAs were called in when they couldn’t break a potential graph, I was hanging back, because pedagogically I had decided – no, that is a lie – because I wanted to find a Harris graph, too. And when working alone wasn’t doing, it, I joined a group as an equal. Improvisation lesson: Think about status. Think about status reversals.
Finally, after about 45 minutes, one graph passed the HGV inspection, the TAs inspection, and my inspection. So I asked the entire class to help confirm. All 23 people in the room gathered around, students, teaching assistants, myself. Painstakingly checking Toughness by mentally deleting accounts and counting how many pieces of the graph remained. Looking for Hamiltonicity by tracing cycles in the air with our fingers.
I said to the class, “This graph is called a Harris Graph. We have proven they exist.”
Quick Math(s) Diversion Because I Must:
This is the formal definition of a Harris Graph:
A Harris graph is a tough, Eulerian, non-Hamiltonian graph.
The Rest of the Tale
Every summer that I teach this course, I tell the students the tale of Harris, and we look for Harris graphs. Some groups find one, some don’t find any. One motivated student wanted to curate a Harris Zoo on the internet, and she worked on it for a while, and then another motivated student (years later) picked it up, and made a website. There will be a link to it below. Students are eager to come up with new Harris Graphs, knowing they will get their discoveries in the Zoo.
I wrote a math education paper about Harris Graphs, and so now they are officially a Thing. I sent a copy to Harris, who was quite pleased.
A student was enthused enough to write code to verify whether a proposed Harris Graph was valid or not. It was too hard for me to use, but another student learned how to use it, and checked the graphs I used as examples in my paper. Ummm… most of them were correct.
A few years later a different student heard me say that I personally couldn’t use the code, and so he wrote different code and a user interface so simple that even Doctor Shaw could use it. Last summer, a student used that code in a program he wrote to find all the Harris graphs with 10 accounts or fewer.
Another student asked me to mentor him on a Harris Graph research project. He told me later that the project helped him get into the university of his choice.
One of my students, Shubhra, became one of my TAs, and she and I started working together on gathering all the results students came up with over the years, including my own results, and writing up a formal paper. We are in that process now. And we’ve added two former students as co-authors, including one who figured out how to take two Harris graphs, and combine them to make a new one! I would strongly recommend collaborating with someone on the other side of the world, by the way – I wake up to see the work she’s done while I’ve slept, and vice-versa. And we can zoom during my morning/her evening. Dozens of students have emailed me, asking me to help them understand mathematics research papers they were reading, on their own, as they researched graph theory results they hoped would help them with their independent Harris graph research.
We are thinking we may have to split this into two math papers.
Harris graphs have inspired students to embrace their love of mathematics, and sometimes to add the subject as a major or minor in college. And now they are a mathematical Thing, and when Shubhra and my graph paper is published, mathematicians who couldn’t care less about the Tale may still be motivated to take them up as a research topic. Over 500 students have looked for Harris graphs. I cannot picture teaching Graph Theory without having a Harris Graph day. But what made it possible? The skills I learned as an improvisor.
Let’s go back to the basic concepts that come up when I teach improv, that came up when I learned it. Listening. Yes-Anding. Status. Inclusivity. Honesty. Vulnerability. Persistence. Spontaneity. Think of your individual pet improv concept – I’ll bet you can find it in the soup above. Mathematics is a large subject, Mathematics Education is a large subject, and this tale was an example of how Improv training affected both of them.
Links! Links! Links!
If you have attempted to find your own Harris Graph, you may want to visit the Harris Graph Zoo! You can find it here: https://tinyurl.com/harriszoo
If you have a graph you want to check, this is Akshay Anands’s program: https://tinyurl.com/harrischecker
If you want to read my first paper on Harris Graphs, from a math education point of view: https://tinyurl.com/harrispaper
If you want to read the second paper on Harris Graphs, from a mathematics point of view… Stay Tuned!