Maths Olympiad Prep

Library / /12 of 12

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it Mongolia

Find the smallest positive number 0<c<10 < c < 1 satisfying the following property:
Any simple, triangle-free graph with n3n \ge 3 vertices, where the degree of any vertex is strictly bigger than cncn, is bipartite.

Explanation: A simple graph is an undirected graph with no loops and no multiple edges. The degree of a vertex is the number of edges connected to that vertex. A triangle is a cycle of length three. A graph is bipartite if it can be colored in two colors in such a way that no edge connects vertices of the same color.

Solution

Answer: c=25c = \frac{2}{5}.
We say that a simple graph with nn vertices is c-good if it is triangle-free and the degree of any vertex is strictly bigger than cncn. A length 5 cycle is triangle-free and the degree of any vertex is 2. For c<25c < \frac{2}{5}, this graph is c-good, but not bipartite.

Now we show that for c=25c = \frac{2}{5}, all c-good graphs are bipartite. Let GG be a triangle-free graph which is not bipartite. We prove that it has a vertex with degree 2n5\le \frac{2n}{5}.

By Euler's theorem, GG contains an odd cycle. Let
C={v1,v2,,vm} C = \{v_1, v_2, \dots, v_m\}
be an odd cycle of minimum length. Since GG is triangle free, we have m5m \ge 5.

First, note that vertices in CC are connected iff they have adjacent indices (modulo mm). Otherwise, an edge connecting two non-adjacent vertices viv_i and vjv_j divides CC into two cycles of combined length m+2m + 2:
{vi,vi1,,vj+1,vj},{vi,vi+1,,vj1,vj}. \{v_i, v_{i-1}, \dots, v_{j+1}, v_j\}, \quad \{v_i, v_{i+1}, \dots, v_{j-1}, v_j\}.
One of these cycles will have an odd length strictly less than mm, which contradicts the minimality of mm.

Similarly, a vertex not in CC can connect to at most two vertices in CC. Indeed, suppose that uCu \notin C is connected to vrv_r, vsv_s, vtCv_t \in C with 1r<s<tm1 \le r < s < t \le m, and consider the three cycles of combined length m+6m + 6:
{u,vr,vr+1,,vs},{u,vs,vs+1,,vt},{u,vt,vt+1,,vr}. \{u, v_r, v_{r+1}, \dots, v_s\}, \quad \{u, v_s, v_{s+1}, \dots, v_t\}, \quad \{u, v_t, v_{t+1}, \dots, v_r\}.
One of these cycles will have an odd length and the other two will have length at least four, since GG is triangle free. Therefore, the odd cycle will have length at most m+644=m2m + 6 - 4 - 4 = m - 2. This again contradicts the minimality of mm.

Finally, let d(u)d(u) denote the degree of a vertex uGu \in G and let d(u,C)d(u, C) denote the number of edges from uu to a vertex in CC. From above, we have d(u,C)2d(u, C) \le 2 for any uGu \in G. Thus we have
vCd(v)=uGd(u,C)2n. \sum_{v \in C} d(v) = \sum_{u \in G} d(u, C) \le 2n.

It follows that there is a vertex vv in CC such that d(v)2nm2n5d(v) \le \frac{2n}{m} \le \frac{2n}{5}. This completes the solution.

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.