Olympiad problems

1990 Czech and Slovak Olympiad III A, 5

In a country every two towns are connected by exactly one one-way road. Each road is intended either for cars or for cyclists. The roads cross only in towns, otherwise interchanges are used as road junctions. Show that there is a town from which you can go to any other town without changing the means of transport.

Russian TST 2019, P2

Tags: polyhedron , edge , combinatorics

Two ants are moving along the edges of a convex polyhedron. The route of every ant ends in its starting point, so that one ant does not pass through the same point twice along its way. On every face $F$ of the polyhedron are written the number of edges of $F$ belonging to the route of the first ant and the number of edges of $F$ belonging to the route of the second ant. Is there a polyhedron and a pair of routes described as above, such that only one face contains a pair of distinct numbers? [i]Proposed by Nikolai Beluhov[/i]

1992 All Soviet Union Mathematical Olympiad, 573

Tags: edge , graph , combinatorics

A graph has $17$ points and each point has $4$ edges. Show that there are two points which are not joined and which are not both joined to the same point.

1975 Bundeswettbewerb Mathematik, 2

Tags: combinatorial geometry , polyhedron , 3d geometry , edge , geometry

Prove that in each polyhedron there exist two faces with the same number of edges.

1998 ITAMO, 2

Tags: combinatorial geometry , polyhedron , 3d geometry , edge , geometry

Prove that in each polyhedron there exist two faces with the same number of edges.

Kvant 2019, M2573

Tags: combinatorics , polyhedron , edge

Two ants are moving along the edges of a convex polyhedron. The route of every ant ends in its starting point, so that one ant does not pass through the same point twice along its way. On every face $F$ of the polyhedron are written the number of edges of $F$ belonging to the route of the first ant and the number of edges of $F$ belonging to the route of the second ant. Is there a polyhedron and a pair of routes described as above, such that only one face contains a pair of distinct numbers? [i]Proposed by Nikolai Beluhov[/i]

2018 Saudi Arabia GMO TST, 4

Tags: edge , graph , combinatorics , graph theory

In a graph with $8$ vertices that contains no cycle of length $4$, at most how many edges can there be?

2019 Romanian Master of Mathematics Shortlist, original P5

Tags: combinatorics , polyhedron , edge

Two ants are moving along the edges of a convex polyhedron. The route of every ant ends in its starting point, so that one ant does not pass through the same point twice along its way. On every face $F$ of the polyhedron are written the number of edges of $F$ belonging to the route of the first ant and the number of edges of $F$ belonging to the route of the second ant. Is there a polyhedron and a pair of routes described as above, such that only one face contains a pair of distinct numbers? [i]Proposed by Nikolai Beluhov[/i]

1990 All Soviet Union Mathematical Olympiad, 513

Tags: point , graph , combinatorics , combinatorial geometry , edge

A graph has $30$ points and each point has $6$ edges. Find the total number of triples such that each pair of points is joined or each pair of points is not joined.

2025 Bulgarian Spring Mathematical Competition, 10.4

Tags: edge , graph theory , deletion , combinatorics

Initially $A$ selects a graph with $ 2221 $ vertices such that each vertex is incident to at least one edge. Then $B$ deletes some of the edges (possibly none) from the chosen graph. Finally, $A$ pays $B$ one lev for each vertex that is incident to an odd number of edges. What is the maximum amount that $B$ can guarantee to earn?

2011 Danube Mathematical Competition, 4

Tags: graph , graph theory , combinatorics , edge

Given a positive integer number $n$, determine the maximum number of edges a triangle-free Hamiltonian simple graph on $n$ vertices may have.