Competition problem — Combinatorics

Library / /264 of 299

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it Iran

Let $G$ be a connected simple graph with vertices $v_1, v_2, \dots, v_{11}$ such that $v_1$ is of degree $2$ and the rest of the vertices are of degree $3$ . Assume that for every subset $A$ of vertices with at most $4$ elements the subset of vertices that are not in $A$ but have an edge connecting them to some elements of $A$ has at least as many elements as $A$ . Find the smallest possible diameter of the graph $G$ .

(Note. A graph is said to be connected if there is a path between every pair of its vertices. The diameter of a graph is the length of the shortest path between the most distanced vertices.)

Solution

We claim that the answer is $12$ . We construct the graph as the following; we shall consider two cases:

First. If the degree of the zero floor vertex is two. Then, we shall have two vertices in the first floor. Assume now for contradiction, then we would have one vertex in the fifth floor of degree three. Therefore, we at least have four vertices in the floors four and five. Thus, we at least have four vertices in the floors three, four, and five connected to these floors. Taking into account that we at least have one vertex in the second floor, we would at least have $12$ vertices, a contradiction.

Analogously, we can refute the case that the degree of the vertex on the first floor is three; indeed, we have four vertices in the first and second floor thus we should at least have four vertices in the fourth floor connected to these floors. If the vertex at the fifth floor is of degree two, we would at least have three vertices in the floors four and five, we shall then at least have $12$ vertices, a contradiction.

We will then show that this graph satisfies the condition of the problem: it is clear that the one elements sets satisfy the condition. The two elements sets also satisfy the statement of the problem since the degree of at least one of their vertices is three. The three elements sets also satisfy the above condition since we have no triangle in the graph and there would at least be eight edges from these three vertices. We shall then prove that the four elements sets also satisfy the condition of the problem; for this reason, we count the number of blue and red vertices in the figure; if all the vertices are on one of the polygons then we at least have one adjacent vertex from the same polygon and three adjacent from the green edges. For sake of simplicity, remove the green edges, if two of them are on a polygon, we should have two adjacent in each polygon. Analogously, if we have three green edges on a polygon and one vertex on another polygon, we are done. ■

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.