Olympiad problems

2018 Saudi Arabia GMO TST, 4

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

1992 All Soviet Union Mathematical Olympiad, 573

Tags: graph , edges , 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.

1990 All Soviet Union Mathematical Olympiad, 513

Tags: graph , combinatorics , combinatorial geometry , points , edges

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.

1990 Czech and Slovak Olympiad III A, 5

Tags: combinatorics , graph theory , edges

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.

2025 Bulgarian Spring Mathematical Competition, 10.4

Tags: graph theory , edges , 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?