Some cities in country are connected by road, and from every city goes $\geq 2008$ roads. Every road is colored in one of two colors. Prove, that exists cycle without self-intersections ,where $\geq 504$ roads and all roads are same color.
Problem
Source: St Petersburg Olympiad 2009, Grade 11, P6
Tags: combinatorics, graph theory
dgrozev
01.09.2017 18:02
So, we have a graph $G$ with $n$ vertices. Every vertex has degree at least $2008$. Every edge is colored with one of two colors. Prove that there exists a monochromatic cycle with at least 504 edges. All edges of $G$ are at least $2008n/2=1004n$. It means there are at least $502n$ edges colored with the same color. Remove all the other edges, thus obtaining a graph $G'$. Let the graph $G'$ has $k$ connected components $G'_1,G'_2,\dots,G'_k$ with correspondingly $n_1,n_2,\dots,n_k$ vertices. For each component $G'_i$ we construct its spanning tree $T_i$ by depth-first search. This algorithm ensures that all edges of $G'_i$ connect only vertices of $T_i$ that are comparable. Now, let us suppose on the contrary, there doesn't exist a cycle of at least $504$ edges. It means for any $T_i$ and any $v\in T_i$ , all vertices $v$ is connected with in $G'_i$ can be lower than $v$ in $T_i$ by no more than $502$ units (because otherwise there will be a $504$ cycle). Having this in mind, let us count the edges of each $G'_i$ . Each vertex of $T_i$ , except the root, is connected downwards (in $G'_i$) with at most $502$ vertices (in $T_i$). It means all vertices of $G'_i$ are at most $502(n_i-1)$, thus all vertices of $G'$ are at most $\sum_{i=1}^k 502(n_i-1)<502n$ , a contradiction.
Pathological
26.05.2019 21:47
Here is a different solution then the above, which is basically a direct application of a few results of the graph theory section of Pascal96's combinatorics book.
Let our two colors be lime green and ice blue . Maintaining the same notations as dgrozev above, we can WLOG assume that there are at least $502n$ ice blue edges. Let $G'$ be the graph of the ice blue edges. Note that the average degree of $G'$ is at least $1004.$
Lemma. (from Pascal96's book) If a graph $G$ has average degree $d,$ then there exists a subgraph $H$ of $G$ where each vertex has degree $>\frac{d}{2}.$
Proof. Continually remove vertices with degree at most $\frac{d}{2},$ it's easy to verify that the average degree is always at least $d$. This process clearly must terminate at some point since $G$ only has finitely many vertices, and when it does we're done.
$\blacksquare$
Use this lemma to obtain a subgraph $H \subseteq G'$ where $H$ has minimal degree $> \frac{1004}{2} = 502.$ Hence, it suffices to show that:
Claim. (also from book, I think) In a graph with minimal degree $\ge d$, there always exists a cycle of length at least $d+1.$
Proof. Take the longest path $v_1v_2 \cdots v_t.$ Since this path cannot be extended, we know that all of $v_t$'s neighbors are among $v_1, v_2, \cdots, v_{t-1}.$ Hence, as there are at least $d$ of them, we have that there exists $i \le t-d$ with $v_i \leftrightarrow v_t.$ Therefore, we have that $v_i v_{i+1} v_{i+2} \cdots v_t v_i$ is a cycle of length at least $d+1$, as desired.
$\blacksquare$
Apply the claim on $H$ to finish.
$\square$