What is a "graph?" For people who study discrete mathematics it is an abstract set of points and lines. One way of visualizing a graph is thinking of the points as cities and the lines as roads which join them.

For example, consider the following six cities: Atlanta, Boston, Chicago, Dallas, Eugene and Flagstaff. Join them by the maximum number of distinct roads (at most one road per pair of cities) possible, subject to each of the restrictions below.

Restriction 1. It must be possible to split the cities into two groups so that cities connected by a road are in different groups.

          With this restriction:

          a.  How many roads are there?

          b.  Can one leave home in Boston, travel along your roads, visit
              every city exactly once, and return home?

          c.  Can one traverse each road exactly once in a given trip?

          d.  Suppose three committees must be formed and the mayors from
              each city must serve on exactly one committee.  If each mayor
              lists two of the three as preferences, is it always possible to
              assign the committees so that each mayor is satisfied and so that
              cities connected by a road have mayors on different committees?

Restriction 2. It must be possible to build the roads without using bridges, tunnels or intersections.

          With this restriction:

          a.  How many roads are there?

          b.  Can one leave home in Boston, travel along your roads, visit 
              every city exactly once, and return home?

          c.  Can the cities always be split into three groups so that cities 
              joined by a road are in different groups?

Under either restriction, questions b and c involve the study of paths and cycles in graphs, the topic of week one. Restriction 2 involves the topic of week two, graph embeddings, which is the study of the surfaces on which a graph is drawn (flat table, basketball, doughnut, etc.). The final week covers the topic of graph coloring, which includes the kinds of questions in parts d above. (In Kindergarten we learned to count, color, and connect the dots. Now we're going to do the same all over again, only this time it will be a little more challenging and a lot more fun!) Can you and a colleague answer any of the questions above?

High school teachers who love mathematics and want to learn more are invited to apply for an all expenses paid, three-week immersion program at the DIMACS Research and Education Institute.

The intent of the DIMACS Research and Education Institute is to integrate education and research in the mathematical and computer sciences. The institute also invites many of the world's foremost researchers in graph theory and combinatorial optimization to participate. In addition to giving technical talks in their areas of expertise, invited researchers will also give lectures designed to be of interest to a more general audience. Participating teachers will have special classes in Discrete Mathematics, Computer Science, and the Foundations of Graph Theory.

DIMACS Home Page

DREI '98 Home