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?

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:
It's always fun to get the audience to participate. 


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" 


Mathematics of juggling: http://www.youtube.com/watch?v=38rf9FLhl8 


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. 


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. 


That's why cat's cradle was invented. 


How large a group? With audiences of 46 people, I've done well just drawing pictures in a notebook and regularly passing it around. 


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. 

