BERKELEY MATH CIRCLE 2000-2001




Graph Theory, Oct. 15, 2000


PAUL ZEITZ
UNIVERSITY OF SAN FRANCISCO

  1. (USAMO 1986) During a certain lecture, each of five mathematicians fell asleep exactly twice. For each pair of these mathematicians, there was some moment when both were sleeping simultaneously. Prove that, at some moment, some three of them were sleeping simultaneously.

  2. Show that every graph contains two vertices of equal degree.

  3. Given six people, show that either three are mutual friends, or three are complete strangers to one another. (Assume that ``friendship" is mutual; i.e., if you are my friend then I must be your friend.)

  4. Seventeen people are at a party. It turns out that for each pair of people present, exactly one of the following statements is always true: ``They haven't met," ``They are good friends," or ``They hate each other." Prove that there must be a trio (3) of people, all of whom are either mutual strangers, mutual good friends, or mutual enemies.

  5. Show that if a graph has $ v$ vertices, each of degree at least $ v/2$, then this graph is connected. In fact, show that it is Hamiltonian.

  6. How many edges must a graph with $ n$ vertices have in order to guarantee that it is connected?

  7. A large house contains a television set in each room that has an odd number of doors. There is only one entrance to this house. Show that it is always possible to enter this house and get to a room with a television set.

  8. A bipartite graph is one where the vertices can be partitioned into two sets $ U,V$ such that each edge has one end in $ U$ and one end in $ V$. The figure below shows two bipartite graphs. The one on the right is a complete bipartite graph and is denoted $ K_{4,3}$. Show that a graph is bipartite if and only if it has no odd cycles.

  9. A group of people play a round-robin chess tournament, which means that everyone plays a game with everyone else exactly once (chess is a one-on-one game, not a team sport). There are no draws.

    1. Prove that it is always possible to line up the players in such a way that the first player beat the second, who beat the third, etc. down to the last player. Hence it is always possible to declare not only a winner, but a meaningful ranking of all the players.

    2. Give a graph theoretic statement of the above.

    3. Must this ranking be unique?

  10. A domino consists of two squares, each of which is marked with $ 0,1,2,3,4,5$, or 6 dots. Here is one example. Verify that there are 28 different dominos. Is it possible to arrange them all in a circle so that the adjacent halves of neighboring dominos show the same number?

  11. Is it possible for a knight to travel around a standard $ 8 \times 8$ chessboard, starting and ending at the same square, while making every single possible move that a knight can make on the chessboard, exactly once? We consider a move to be completed if it occurs in either direction.

  12. (IMO 1991) Let $ G$ be a connected graph with $ k$ edges. Prove that the edges can be labeled $ 1, \dots, k$ in some fashion, such that for every vertex of degree greater than 1, the labels of those edges incident to that vertex have greatest common divisor 1.

  13. (USAMO 1989) The 20 members of a local tennis club have scheduled exactly 14 two-person games among themselves, with each member playing in at least one game. Prove that within this schedule there must be a set of 6 games with 12 distinct players.

  14. An $ n$-cube is defined intuitively to be the graph you get if you try to build an $ n$-dimensional cube out of wire. More rigorously, it is a graph with $ 2^n$ vertices labeled by the $ n$-digit binary numbers, with two vertices joined by an edge if the binary digits differ by exactly one digit. Show that for every $ n \geq 1$, the $ n$-cube has a Hamiltonian cycle.

  15. Even if a graph is not planar, it is still possible to ``embed" it on a surface. This concept can be made more rigorous, but should be intuitively clear. For example, $ K_5$ is not planar, but it can be embedded on a torus! Show how this can be done.

  16. If you place the digits 0,1,1,0 clockwise on a circle, it is possible to read any two-digit binary number from 00 to 11 by starting at a certain digit and then reading clockwise. Is it possible to do this in general?

  17. The Two Men of Tibet. Two men are located at opposite ends of a mountain range, at the same elevation. If the mountain range never drops below this starting elevation, is it possible for the two men to walk along the mountain range and reach each other's starting place, while always staying at the same elevation? Here is an example of a ``mountain range." Without loss of generality, it is ``piecewise linear," i.e., composed of straight line pieces. The starting positions of the two men is indicated by two dots.

  18. A rectangle is tiled with smaller rectangles, each of which has at least one side of integral length. Prove that the tiled rectangle also must have at least one side of integral length.