Olympiad problems

KoMaL A Problems 2021/2022, A. 807

Let $n>1$ be a given integer. Let $G$ be a finite simple graph with the property that each of its edges is contained in at most $n$ cycles. Prove that the chromatic number of the graph is at most $n+1$.

2016 Croatia Team Selection Test, Problem 2

Tags: graph theory , spanning tree , graph coloring , combinatorics

Let $S$ be a set of $N \ge 3$ points in the plane. Assume that no $3$ points in $S$ are collinear. The segments with both endpoints in $S$ are colored in two colors. Prove that there is a set of $N - 1$ segments of the same color which don't intersect except in their endpoints such that no subset of them forms a polygon with positive area.

2016 IMAR Test, 3

Tags: graph theory , graph , spanning tree , combinatorics , combinatorial geometry

Fix an integer $n \ge 2$, let $Q_n$ be the graph consisting of all vertices and all edges of an $n$-cube, and let $T$ be a spanning tree in $Q_n$. Show that $Q_n$ has an edge whose adjunction to $T$ produces a simple cycle of length at least $2n$.

2008 IMS, 4

Tags: graph theory , spanning tree , square grid , combinatorics

A subset of $ n\times n$ table is called even if it contains even elements of each row and each column. Find the minimum $ k$ such that each subset of this table with $ k$ elements contains an even subset

2023 All-Russian Olympiad Regional Round, 11.10

Tags: graph theory , combinatorics , spanning tree , aro

Given is a simple connected graph with $2n$ vertices. Prove that its vertices can be colored with two colors so that if there are $k$ edges connecting vertices with different colors and $m$ edges connecting vertices with the same color, then $k-m \geq n$.

2001 239 Open Mathematical Olympiad, 8

Tags: combinatorics , graph theory , spanning tree

Assume that the connected graph $G$ has $n$ vertices all with degree at least three. Prove that there exists a spanning tree of $G$ with more than $\frac{2}{9}n$ leaves.

2016 Croatia Team Selection Test, Problem 2

Tags: graph theory , spanning tree , graph coloring , combinatorics

Let $S$ be a set of $N \ge 3$ points in the plane. Assume that no $3$ points in $S$ are collinear. The segments with both endpoints in $S$ are colored in two colors. Prove that there is a set of $N - 1$ segments of the same color which don't intersect except in their endpoints such that no subset of them forms a polygon with positive area.

2017 239 Open Mathematical Olympiad, 8

Tags: combinatorics , graph theory , spanning tree

Assume that the connected graph $G$ has $n$ vertices all with degree at least three. Prove that there exists a spanning tree of $G$ with more than $\frac{2}{9}n$ leaves.

2025 Bulgarian Spring Mathematical Competition, 9.3

Tags: combinatorics , connected graph , graph theory , dominating sets , spanning tree , algorithm

In a country, there are towns, some of which are connected by roads. There is a route (not necessarily direct) between every two towns. The Minister of Education has ensured that every town without a school is connected via a direct road to a town that has a school. The Minister of State Optimization wants to ensure that there is a unique path between any two towns (without repeating traveled segments), which may require removing some roads. Is it always possible to achieve this without constructing additional schools while preserving what the Minister of Education has accomplished?

2020 USA EGMO Team Selection Test, 5

Tags: combinatorics , graph theory , graph cycles , spanning tree

Let $G = (V, E)$ be a finite simple graph on $n$ vertices. An edge $e$ of $G$ is called a [i]bottleneck[/i] if one can partition $V$ into two disjoint sets $A$ and $B$ such that [list] [*] at most $100$ edges of $G$ have one endpoint in $A$ and one endpoint in $B$; and [*] the edge $e$ is one such edge (meaning the edge $e$ also has one endpoint in $A$ and one endpoint in $B$). [/list] Prove that at most $100n$ edges of $G$ are bottlenecks. [i]Proposed by Yang Liu[/i]