(From Finkbeiner and Lindstrom) The Board of Directors of XYZ Corporation has 16 members and 6 committees of 5 persons each as indicated by the following chart.

How many distinct meeting times are needed to conduct the committee meetings of the board?

Draw a graph in which the total degree — that is, the sum of the degrees of each node — is odd.

The graph we used to represent bordering countries in problem 4 was planar. Create a map of your own countries for which the corresponding graph is nonplanar.

A graph is complete when every node is connected to every other node by an edge. Here’s a complete graph with four nodes:

Draw:

A complete graph with five nodes.

A complete graph with six nodes.

A complete graph with three nodes.

How many edges will a complete graph with each of the following number of nodes have?

Five nodes

Six nodes

Three nodes

How would you calculate the number of edges of a complete graph with…

A hundred nodes?

n nodes?

Now that you know how the number of nodes and edges in a complete graph are related, investigate this relationship further.

Are the number of nodes and the number of edges in a complete graph related directly? That is, if you double the number of nodes, does the number of edges double, too?

Are the number of nodes and edges in a complete graph related linearly? Or does the number of edges go up “faster” or “slower” than in a linear relationship?

What’s the minimum number of nodes needed for a graph with 1000 edges, if at most one edge can connect two nodes, and no edge can connect a node to itself?

If a complete graph has 500 nodes, can you estimate the number of edges quickly? Is it more likely to be roughly 12500, 125000, or 1250000 edges?

In the complete graph with four nodes, pictured earlier, the graph is drawn so that some of the edges crossed. However, just because it is drawn that way in that particular diagram does not mean the graph is not planar.

Is the complete graph with four nodes planar?

Is the complete graph with five nodes planar?

How about complete graphs with more than five nodes?

The symbol “Deg,” as in the degree of a node, represents a function. What kinds of objects does Deg take as input? What kinds of objects does it output? By the way, the set of allowable inputs to a function is called its domain, and the set of allowable outputs is called its range.

In this “Clue” game board, draw a graph in which you show which rooms can be reached from the others by the roll of a 6 on a die. Include the secret passages that you can take no matter what you roll from the Lounge to the Conservatory and from the Kitchen to the Study. If you roll a number higher than the number of spaces you need, you can still go in the room. By the way, is the Clue graph planar?

A group of six sophomores is going down to the Lower School to read to a group of six first-graders. The teachers asked for a list of preferences, both from the first-graders and the sophomores, as to who would read to whom.

Is there a way to form partners that will make everybody happy?

(From Epp) A traveler in Europe wants to visit each of six cities shown on this map exactly once, starting and ending in Brussels.
The distance (in kilometers) between each pair of cities is given in the table. Suggest a sequence of cities she can visit that minimizes the distance traveled.

Wiki-Racing! The game of wiki-racing involves starting on a randomly generated Wikipedia page and taking Wikipedia links to navigate through until you reach a designated ending page. For example, two players on two different computers might agree to end on the page for “Fruit Bat.” The first player to arrive at the Fruit Bat Wikipedia page using only the links on Wikipedia pages would win.

Below is a list of webpages in our miniature version of wiki-racing. Each webpage links to some, but not necessarily all, of the others.

How could you represent this situation using a graph?

What is the fewest number of clicks it will take to go from the Toy Story page to the Toy Story 3 page? From the Toy Story page to the Buzz Lightyear page?

Oh, no — your parents just announced that they’re dropping by your apartment for a surprise visit. But your place is a mess. Fortunately, you’ve got some elves — as many as you need — to help you clean the place, but even an elf can’t wash lights with darks. Here’s what you and the elves have got to do, and the time it takes to do each thing:

• Wash your load of light-colored laundry
  (30 mins)
• Wash your load of dark-colored laundry
  (30 mins, and remember you’ve only got one washer)
• Dry your lights (45 mins, and you have to wash the lights first)
• Dry your darks (45 mins, you have to wash the darks first, and you’ve only got one dryer)
• Scrape off the dishes in your sink (10 mins)
• Load and run the dishwasher
  (60 mins, and you have to scrape first)
• Pick your stuff up off of the floor
  (20 minutes)
• Vacuum (10 minutes, and you have to pick up your stuff first)

Find a good graph-theory way to represent this problem. How long will it take you to put your apartment in order?

What is the minimum number of elves you need to do everything in that amount of time?

You have a ${3 \times 3 }$ chessboard. The black knights are in the top two corners, and the white knights are in the bottom two corners. No other pieces are on the board. (Recall that the only moves knights are allowed to make is “2 up or down, 1 left or right,” or “1 up or down, 2 left or right,” but that they can “jump” pieces.)

How many moves will it take to switch the position of the knights, so that the black knights are now in the bottom two corners and the white knights are in the top two corners?

How many moves will it take just to switch the two rightmost knights?

Below is a map of the town of Königsberg, Prussia, as it existed in the 18th Century. A popular puzzle at the time was to cross all seven bridges without ever going back over a bridge you’ve crossed, and wind up at your starting point. Solve the puzzle yourself. (The mathematician Leonhard Euler invented graph theory by analyzing this problem.)

Image from solipsys.com.uk/new/KoenigsbergImages.html

For each figure, say whether you can trace it with your pencil without going over any segment twice, ending at your starting point.

A graph that can be traced in the manner of the previous problem is said to have an Euler Circuit, named after the mathematician who invented graph theory. Propose a method for determining if a given graph has an Euler circuit or not. (Are any of the concepts you’ve learned in this lesson relevant?) Make up new examples to test, if necessary.

Which complete graphs have Euler circuits?

The Irish mathematician William Rowan Hamilton invented a game in the 1850s called the Icosian Game. In it, you had to visit a list of cities connected by roads, as represented by the graph below.

(image from mathworld.wolfram.com/ IcosianGame.html)

The challenge was to start in one city and follow the roads to visit all the cities, winding up at your starting city without ever having visited a city twice. Solve the Icosian Game.

If you read the previous problem carefully, you won’t be surprised to learn that a circuit of the type you found — one where you need to visit each node exactly once and return to your starting node — is called a Hamiltonian circuit. Find Hamiltonian circuits for each graph below.

Do you suppose that all graphs have
Hamiltonian circuits?

Don’t use a calculator for this problem.

Factor ${x^2} + 8x + 16$

Factor ${x^2} - 16$

Solve for $x$: ${x^2} - 5x + 6 = 0$

Subtract $4 \frac{7}{5} - 2 \frac{1}{3}$

If $x^2+y^2=30$ and ${(x + y)^2} = 484$ , what is $xy$ ?

The diagram below shows a blueprint of three different utility companies and three houses. You want to add to the blueprint lines running from each utility company to each house, but the lines cannot cross one another. Suggest a way to do this or argue that it is impossible.

Draw a complete bipartite graph between two groups of two nodes. This graph is abbreviated $K_{2,2}$. Now draw $K_{2,4}$. Using this notation, what graph were you working with in Problem 43?

How many colors are needed to color the graph $K_{2,4}$? How about $K_{m,n}$?

Find a formula for the total degree
of $K_{m,n}$.

In the three-utilities puzzle (see problem 43), suppose now that lines are allowed to cross, and so the lines are actually run that way. If you accidentally cut one of the pipes without knowing which one it is, what’s the probability that the gas in the leftmost house will go out? How about if there are $m$ houses and $n$ utilities, instead?

Any graph that could represent “who beat whom” in a situation where each team plays every other team once is called a tournament. Which of the graphs below are tournaments?

The Game of Sprouts: Mark a few dots on a piece of paper. A move consists of two actions: connect two different dots with a single edge then place a dot at around the middle of this edge. You can only connect two dots if each has a degree of less than 3, and you may not repeat an edge or cross edges. The person who has no move is the loser.

If you start with only two dots, then what is the maximum number of moves the game can last?

At the end of the two-dot sprouts game, what will be the total degree of the diagram?

At the end of the $n$-dot sprouts game, what will be the total degree of the diagram?

How many moves will the $n$-dot sprouts game take?

The following is a floor plan of a house. Is it possible to enter the house in room A, travel through every interior doorway of the house exactly once, and exit out of room E?

Earlier we learned that if two graphs are isomorphic, each node has a "partner" of the same degree. Is it also true that when nodes can be matched into partners having the same degree, the two graphs must be isomorphic?

Propose a criterion by which you’d be able to tell if a graph has an Euler path. Does it matter which nodes are your starting and ending points? Remember to examine a similar problem by making up specific cases for yourself.

In problem 32 and the tournament
problem (see problem 48), you drew a directed graph — a graph where the edges are one-way. The question of finding Euler circuits is more complicated on directed graphs. Do some experiments and propose criteria for whether a directed graph has an Euler circuit.

Does every tournament have a Hamiltonian path? What does it mean for the team rankings if there is more than one path through a tournament?

Come up with your own system to determine the winner of a tournament. It may help to create some of your own examples of tournaments.

The following graph represents streets and corners; the portion of a street between two corners is a “block”. The neighborhood association decides to place streetlights at some of the various corners so that the neighborhood never gets too dark at night. They want there to be enough streetlights so that every home is on a block that has a streetlight on at least one of its corners. Assume that there are homes between each pair of adjacent corners. Find the smallest number of street lights needed.

Use a graph to represent and solve the following maze.

The “doughnut” shape below is called a torus. You know you can’t draw a complete graph with five nodes on a flat surface. But can you draw it on the surface of a torus?

If the blueprint for the houses and utilities (see problem 43) were printed on paper shaped like a torus, could you run the wiring with no overlaps?