Graph Theory (J)

Problems

1. Prove that in any connected graph, any two longest paths intersect.

2. Prove that a graph with no cycles and at least one edge has at least two vertices of degree 1.

3. Prove that amongst six people, we can find a group of three who are either all friends or all not friends.

4. (IMO 1964) Each pair from 17 people exchange letters on one of three topics. Prove that there are at least 3 people who write to each other on the same topic.

5. Prove that a graph is traversible if and only if it has either 0 or 2 vertices of odd degree.

6. n ≥ 2 people meet in a room. Everyone shakes hands with everyone else. Prove that during the greeting ceremony there are always two people who have shaken the same number of hands.

7. Prove that a graph is bipartite if and only if it contains no cycles of odd lengths.

8. A polyhedron with an even number of edges is given. Prove that an arrow can be placed on each edge so that each vertex is pointed to by an even number of arrows.

9. Suppose a graph has n vertices and 2m edges. Show that we can divide the vertices into two groups such that there are at least m + 1 edges ‘broken’.

10. Prove that a graph with n vertices and more than n^{2}/4 edges must contain a triangle.

11. (Klamkin) Ten airlines serve a total of 1983 cities. There is a direct service (no stopover) between any two cities, and if an airline offers a direct flight from A to B, it also offers a direct flight from B to A. Prove that at least one of the airlines provides a round trip with an odd number of landings.

12. Find the smallest n > 4 for which there exists a set of people such that

(a) any two acquaintances have no common acquaintance.

(b) any two unacquainted people have exactly two common acquaintances.

NB: if A is acquainted to B, then B is acquainted to A.

13. Each of the members of parliament in the land of Achronia has exactly one friend and one enemy among the other members of parliament. Prove that the parliament can be divided into two chambers so that inside each of the chambers there are no friends and no enemies.

14. There is a finite number of towns in a country. They are connected by onedirection roads. It is known that, for any two towns, one of them can be reached from the other one. Prove that there is a town such that all the remaining towns can be reached from it.

15. Every road in Sikina is one-way. Every pair of cities is connected by one direct road. Show that there exists a city which can be reached from every other city directly or via at most one other city.

16. There are N towns connected by 2N − 1 one-way roads. Suppose that it is possible to reach any town starting at any other one. Prove that there exists a road that can be closed while preserving the above condition.

17. (1987 AMO) In the country Patera, there are 20 cities and two airline companies, Green Planes and Red Planes, to provide communication between cities. The flights are arranged as follows.

(a) Given any two cities in Patera, one and only one of the companies provides direct flights (in both directions and without stops) between the two cities.

(b) There are two cities, A and B in Patera such that a journey cannot be made (with possible stops) using only Red Planes.

Show that, given any two cities in Patera, a passenger can travel from one to the other using only Green Planes, making at most one stop in some third city.

18. (1988 AMO) A city has a system of bus routes laid out such that

(a) There are exactly 11 bus stops on each route,

(b) It is possible to travel between any two bus stops without changing routes,

(c) Any two bus routes have exactly one bus stop in common.

What is the number of bus routes in the city?

19. If a graph on n vertices has e edges, show that it has at least \frac{e}{3n}(4e − n^{2}) triangles.