I need to give a math talk to a group of undergraduates. I am asking for advice because this talk will take place at a department picnic and there will be no blackboard or projector. I would like to talk about graph theory/combinatorics and I could conceivably use props or handouts. Does anybody have any suggestions?

1$\begingroup$ The department probably has easels available, if you want to lug one to the picnic. $\endgroup$– Theo JohnsonFreydSep 14, 2011 at 17:22

1$\begingroup$ You are right in your assumption; I don't have a topic in mind yet. I am open to anything as long as it is within the realm of graph theory/combinatorics. $\endgroup$– Louis DSep 14, 2011 at 17:46

5$\begingroup$ I saw a great elementary talk on Conway's rational tangles once, using nothing but lengths of rope and volunteers (and an outstanding speaker/performer). $\endgroup$– MartySep 14, 2011 at 17:59

1$\begingroup$ Perhaps you could talk about Ramsey Theory. This would be easy enough to get across to everyone without the use of a blackboard, and you could use volunteers. $\endgroup$– DavidSep 14, 2011 at 18:43

1$\begingroup$ I like using Polydrons for polyhedra with regular faces. You can use chalk on them. However, they are small for a presentation to many people, and if you use Polydron models you would have to pass them around to be effective. $\endgroup$– Douglas ZareSep 14, 2011 at 18:46
11 Answers
If you've got a group of 20 to 30, a fun "audience participation" talk for a picnic could be given on the Josephus problem (participants are put in a circle and every other one is eliminated until a single one remains), perhaps presented as "Survivor: Math Island." Have the students form a circle, hand one of them a token "sword" to start things off, and then insert yourself cleverly in the crowd so as to be the sole survivor. You can have the group next split into subgroups to experiment with different starting numbers and let them discover the poweroftwo basis behind the survivorship algorithm, and you can wrap things up by talking about what's known and not known for variants where you knock out every third or fourth person going around the circle, instead of every second.
Get all the students to stand up. Each student is a vertex. Take some string or rope to model the edges.
Then you can:
 Cover "the first theorem of graph theory"
 Get them to arrange themselves as regular graphs
 Cover the traveling salesman problem by getting them to pass around some object (the salesman) but only if they are connected by an edge (the string)
It's always fun to get the audience to participate.

2$\begingroup$ Also: challenge them to prove that their graph is planar by eliminating all crossings. $\endgroup$ Sep 15, 2011 at 1:24
I might recommend coin tossing as a topic, which is somewhat combinatoricy? Two examples. First, "spinning a penny instead of tossing it results in heads only about 30% of the time" (MathWorld, from Paulos). This should be detectable in an experiment run with the group, and would be quite surprising.
Second, the expectations of runs (consecutive Heads or consecutive Tails) of different lengths are distinctive enough so that it is possible to reliably distinguish between a true random sequence and a "fake" random sequence. Ask them to both write down strings of H's and T's, and generate truly random strings from coin flipping, without revealing which to you. Then you magically uncover which are real and which not. This idea is due to Pál Révész. See his "Strong theorems on coin tossing" (PDF). See also Mark Schilling's "The longest run of heads" (PDF). You could connect this to discrepancy theory to show it is not just play.
Then you could mention the recent DiaconisHolmesMongomery work on "Dynamical bias in the coin toss" (PDF).
If you want them to listen to everything you say, you will have to reinforce your speaking/oratory skills. If instead you want them to learn, give them something to think about and play with while you are talking. Have scratch paper and pencils and encourage their use. Alternatively, have one or two (not more than two) items to use as a visual focus as well as a subject for the talk.
As an example, I had to TA a section that involved teaching (something like) the change of variable technique for multiple integrals. I took them to a place on campus that had a hemispherical skylight at eye level with some gridlines on it, where you could see the shadow of the lines on the floor below. I used this as an example of how one needs to be concerned about how volume elements change as you try to approximate the integral, and why you needed the determinant to represent this change.
If you were to do something similar (say Leonardo da Vinci's observation about how flow at the mouth of the river was the sum of the flows at the branches), you might invoke a tree or idealization thereof to get your point across. Also, don't expect to have the aid carry the audience through the talk for more than about 10 minutes on a single topic. You can reuse it for more than one topic though.
Gerhard "Ask Me About Minimalist Environments" Paseman, 2011.09.14
Maybe this isn't exactly graph theory but it is kind of combinatorial...
You could talk about the 5 platonic solids (someone in your department may have models of these sitting around). Discuss the orbitstabilizer theorem and then use it to count the number of (rotational) symmetries of the solids. I find that most people are surprised to find out that counting the rotational symmetries of the dodecahedron is as simple as "12 faces times 5 rotations fixing a face = 60 rotational symmetries"

$\begingroup$ Count me as another surprised person. :) $\endgroup$ Sep 14, 2011 at 18:20

3$\begingroup$ Even more low tech: the position of the dodecahedron is determined by which of the 12 faces is in front, and by which of the 5 edges of that face is on the bottom. $\endgroup$ Sep 14, 2011 at 19:27

2$\begingroup$ Uh, looks like there's a blackboard there. And I don't suppose you can improvise that without a lot training... $\endgroup$ Sep 14, 2011 at 18:27

3$\begingroup$ When I give this talk at juggling conventions I don't usually have a blackboard. $\endgroup$ Sep 15, 2011 at 12:27
For a good 15minute exercise for undergraduates, I like Heidi Burgiel's paper on how even a perfect Tetris player must eventually lose with probability one. I've given it as a talk before with almost no boardwork, and that was only to prove more rigorously some ideas that are pretty intuitive: that the best way to stack Ss and Zs vertically is by putting likeonlike, which I think most undergrads are happy to believe with just a little handwaving.

$\begingroup$ See also, "Tetris is Hard, Even to Approximate" by Erik Demaine, Susan Hohenberger, and David LibenNowell: erikdemaine.org/papers/Tetris_COCOON2003 . This could add a bit to a Tetris presentation. $\endgroup$ Sep 14, 2011 at 23:04
Thank you to everybody for the great suggestions. I have decided what to do (see below) and I'll let you know how it goes after the picnic next week. I was inspired by the audience participation aspect of Josephus problem suggestion.
I will ask for a group of say 11 volunteers and ask them to shake hands with each other so that they all shake exactly three hands. Of course this is impossible and I will explain why. I may ask them if they can do this with an even number of people and have them try to come up with the construction.
Next I will describe a triple handshake (a group hug might be awkward...) and ask a group of 7 volunteers if they can do triple handshakes so that every pair of people are involved in exactly one triple handshake. Of course this is challenging without thinking about it for a while, but I will show them how to do it after they try. Then I will ask them if this can happen with 8 people. Again this is impossible and I will explain why. Now that we know there can be no "special triplehandshake system" (STS) on an even number of vertices I will explain why it can't happen with some odd numbers, like 11 for instance.

$\begingroup$ Most people will behave normally about social contact; bring some handiwipes or alternative (perhaps a witty remark by Adrian Monk) and offer its use. Gerhard "Has A Runny Nose Now" Paseman, 2011.09.16 $\endgroup$ Sep 16, 2011 at 15:28

$\begingroup$ Also, it will be interesting to see if they start with two separate groups of three for the triple handshake. Do you have a nice proof of impossibility (is there one even?) for this case? Gerhard "Ask Me About System Design" Paseman, 2011.09.16 $\endgroup$ Sep 16, 2011 at 15:32

$\begingroup$ (It took me a few minutes to come up with an impossibility proof in case the STS construction on 7 points attempts to start with two disjoint triples; whatever proof you have, you should practice it at least twice in front of one or two people before giving it to your group. I've had unrehearsed things go badly on me.) Gerhard "Ask Me About System Design" Paseman, 2011.09.16 $\endgroup$ Sep 16, 2011 at 15:39

$\begingroup$ The handshake activities sound terrific. One potential pitfall for the triple handshake problem, however, is that students may lose track of who they have or haven't shaken hands with, especially if they've made several attempts at a solution (and especially if there's been beer at the picnic). I've had that happen in a demo where people were supposed to pairwise toast one another with wine glasses. $\endgroup$ Sep 16, 2011 at 20:53
How large a group? With audiences of 46 people, I've done well just drawing pictures in a notebook and regularly passing it around.

$\begingroup$ I'm thinking there may be 20 people although I don't know for sure. This include students and other faculty who may be at the picnic. $\endgroup$– Louis DSep 14, 2011 at 17:39
It is brave of you to accept this task and I wish you luck.
One possibility would be the 27 lines on a smooth cubic surface and their incidence graph (and the fact that this picture is independent of the surface). Plaster models of cubics that exhibit the lines do exist and such a model would be a perfect prop.