Graph Theory 1

0.1 Graph Theory

stuck? try these: Turning grids into graphs

• One common way to turn a grid into graphs is to create a bipartite graph
between the columns and rows such that ci and r j are connected iff (i, j) is
marked. This way we can find cycles alternating row and column.

• Creating a bipartite graph between all rows and columns and particular objects.
This helps to prove matching.

Lemma 1 (Bipartite Graph) — Any graph having only even cycles are Bipartite.

1 AoPS 3 Problem
2 ISL 2004 C3 4 Problem

Theorem 2 (Euler’s Polyhedron Formula) — For any polyhedron with E,V, F edges, vertices’s
and faces resp. the following relation holds

V +F = E +2

In a planar graph with V vertices, E edges and C cycles, the following condition is always satisfied:

V +C = E + 1

Lemma 3 (Criteria of partitioning a graph into disconnected sub-graphs) — If there exist

no three vertices, u, v, w that uv ∈ E(G) also uw, vw ∈ E(G), the graph can be partitioned into
equivalence classes based on their non-neighbors.

Problem 1 (China TST 2015 T1 D2 P3). There are some players in a Ping Pong tournament,
where every 2 players play with each other at most once. Given:
1. Each player wins against at least a players, and loses to at least b players. (a, b ≥ 1)
2. For any two players A, B, there exist some players P1 , ..., Pk (k ≥ 2) (where P1 = A,Pk =
B), such that Pi wins against Pi+1 (i = 1, 2..., k − 1)
Prove that there exist a + b + 1 distinct players Q1 , ...Qa+b+1 , such that Qi wins against
Qi+1 (i = 1, ..., a + b).

Remark. Typical largest path, some workaround with given constraints problem.
Graph Theory 2

Solution. Take the largest path starting from a1 to an .

Definition— Assume that n ≤ a + b. Since this is the largest path, a edges

coming out of an are all in S = {a1 , a2 , . . . an }, and b edges going in a1 are all in
S. Let S1 be the set of vertices that an wins against, and S2 be the set of vertices
that a1 loses against. Moreover, let al be the smallest element of S1 , and an−k be
the largest element of S2 (smallest means leftmost in the part, and largest means
rightmost).

Let S′ = {al , al+1 , . . . an−k−1 , an−k }. Since n ≤ a + b, we have S′ ̸= ∅.

We also define:

S1′ = {ai | ai defeats ai+1 where ai+1 ∈ S1 ∩ S′ }

S2′ = {ai | ai−1 defeats ai where ai−1 ∈ S2 ∩ S′ }

Figure 0.1.1

Now, note that for any x ∈ S2′ , y ∈ S1′ , there is a path between x, y with n vertices.
So for all x ∈ S2′ , there does not exist a vertex outside of S that defeats x. And for
all y ∈ S1′ , there doesn’t exist a vertex outside of S that loses to y, because of the
maximality of n.

We show that, S1′ ∩ S2′ ̸= ∅. Then there would exist a vertex that doesn’t have any
edge outside of S, meaning it has at least a + b games inside S, proving the result.

We have, S1′ , S2′ ⊂ S′ ∪ {al−1 , an−k+1 }. We have,

|S1′ | ≥ a − k + 2 [∵ an has at most k − 2 vertices in {an−k+1 , . . . an }]

|S2′ | ≥ b − l + 3

But |S′ | = n − (l − 1) − (k) + 2 ≤ a + b − l − k + 3 < |S1′ | + |S2′ |. So S1′ ∩ S2′ ̸= ∅, and we

are done.
 Graph Theory 3

Problem 2 (ARO 2005 P10.8). A white plane is partitioned in to cells (in a usual way). A
finite number of cells are coloured black. Each black cell has an even (0, 2 or 4) number
of adjacent (by the side) white cells. Prove that one may colour each white cell in green or
red such that every black cell will have equal number of red and green adjacent cells.

Solution. First we join the white cells like this:

Figure 0.1.2

Now, notice that the plane have been divided into some cycles (a black cell that has
no adjacent black cells is a cycle itself). So we can color the plane blue and yellow in
a way that no region has the same color as its neighbors. We can do this because at
any junction, there are an even number of regions connected because of the problem
condition.

Now we focus on our graph that we created connected the white cells. Take any cycle
on it. If we have a “slanted” edge, then both of the nodes are inside a region of either
blue or yellow. But in a “straight” edge, the two nodes are in different colored region.

We know that there are an even number of slanted edges, which is trivial to prove
(using the fact that any cycle on a grid system has even number of nodes, and on
these cycles, most of the edges (the straight ones) have even lenght, but only the
slanted one has odd lenghts on the sides). It is also easy to see that there are an even
number of straight edges, because of going in and out of the regions of a fixed color.

So our cycle has an even number of nodes and thus bipartite. We can color the graph
with two colors, so that along each edge, the two nodes are of different color.

Remark. There is a simple coloring using this solution. After we color the regions of
the plane with blue and yellow, we number each column with integers. Then on the odd
numbered columns, we color all the white cells that are in yellow region green and blue
region red. And on the even numbered columns, we do the opposite. It is easy to check
that this coloring works using the graph we created before.

Problem 3 (AtCoder GC033 C). Takahashi and Aoki will play a game on a tree. The tree
 Graph Theory 4

has N vertices numbered 1 to N , and the i-th of the N − 1 edges connects Vertex ai and
Vertex bi
At the beginning of the game, each vertex contains a coin. Starting from Takahashi, he
and Aoki will alternately perform the following operation:

• Choose a vertex v that contains one or more coins, and remove all the coins from v.

• Then, move each coin remaining on the tree to the vertex that is nearest to v among
the adjacent vertices of the coin’s current vertex.

The player who becomes unable to play, loses the game. That is, the player who takes his
turn when there is no coin remaining on the tree, loses the game. Determine the winner of
the game when both players play optimally.

Solution. First transform the game by removing the idea of coins, and replacing it with
deleting vertices. Now, notice that the longest path in this tree (i.e. the diameter)
strictly decreases by 1 or 2 each turn depending on the move. So it’s just a basic
predetermined game.

Problem 4 (ARO 1999 P9.8). There are 2000 components in a circuit, every two of which
were initially joined by a wire. The hooligans Vasya and Petya cut the wires one after
another. Vasya, who starts, cuts one wire on his turn, while Petya cuts one or three. The
hooligan who cuts the last wire from some component loses. Who has the winning strategy?

Solution [Copycat]. The P-Hooligan Petya has a winning strategy, for he can be follow
the old cunning trick of never losing. How does he do it?
He starts by secretly partitioning the vertices in two 1000 degree subsets. He calls
them A = {a1 , a2 . . . a1000 } and B = {b1 , b2 . . . b1000 }. He then connects ai with bi with
an edge with an invisible marker that only he can see.
Now the game begins. Petya copies Vasyas moves following these rules:

1. If Vasya removes an edge ai – a j , where i ̸= j, then Patya removes the edges ai

– b j , a j – bi and bi – b j .

2. If Vasya removes a j – bi , where i ̸= j, then Patya removes the other three edges
from the above rule.

3. If Vasya removes ai –bi , then Patya looks for another b j , such that ai –b j exists.
Then by the symmetry so far maintanined, a j –bi and a j –b j exist too. And Patya
can remove a j –b j , and swap the names of b j and bi .
But if he can’t, then that would mean after Vasya’s move ai would become
isolated, and Patya would win.
 Graph Theory 5

It is easy to see that the above moves are possible since Patya is always maintaining
symmetry between A, B. So he can’t move means Vasya has already disconnected one
of the vertices.

Remark. The case with 4 vertices and 6 vertices give an idea to copy the opponent’s
moves.

Problem 5 (ISL 2001 C3). Define a k-clique to be a set of k people such that every pair
of them are acquainted with each other. At a certain party, every pair of 3-cliques has at
least one person in common, and there are no 5-cliques. Prove that there are two or fewer
people at the party whose departure leaves no 3-clique remaining.

Solution. Casework with the point where most of the triangles are joined.

Problem 6 (ARO 2017 P9.1). In a country some cities are connected by one-way flights
(there is at most one flight between two cities). City A is called “available” from city B, if
there is a flight from B to A, maybe with some transits. It is known, that for every 2 cities
P and Q, there exists a city R, such that P and Q are both available from R. Prove, that
exist city A, such that every city is available from A.

Solution. Basic induction exercise.

Problem 7 (Tournament of Towns 2009 S6). Anna and Ben decided to visit a country with
2009 islands. Some pairs of islands are connected by boats which run both ways. Anna and
Ben are playing during the trip:
Anna chooses the first island on which they arrive by plane. Then Ben chooses the next
island which they could visit. Thereafter, the two take turns choosing an island which they
have not yet visited. When they arrive at an island which is connected only to islands they
had already visited, whoever’s turn to choose next would be the loser. Prove that Anna
could always win, regardless of the way Ben played and regardless of the way the islands
were connected.
Solution. The copycat idea, as always in games. How can Anna make sure she gets a
move after Ben? Maybe she can “pair” vertices and follow them along. What happens
if she tries this strategy?

Problem 8 (USA TST 2014 P5). Find the maximum number E such that the following holds:
there is an edge-colored graph with 60 vertices and E edges, with each edge colored either
red or blue, such that in that coloring, there is no monochromatic cycles of length 3 and
no monochromatic cycles of length 5.
 Graph Theory Counting in Graph 6

0.1.1 Counting in Graph

Lemma 4 (Average of Degrees) — In a graph G with n vertexes, let E be the set of all edges.
Assign an integer fi to every vertex vi such that fi equals to the everage degree of the neighbors of
vi . We have,
n
∑ fi ≥ 2|E|
i=1

Lemma 5 — In a graph G with n vertexes, let E be the set of all edges. Assign an integer gi to
every vertex vi such that gi equals to the maximum degree among its neighbors. We have,
n
∑ gi ≥ 2|E|
i=1

Problem 9 (USA TST 2014 P3). Let n be an even positive integer, and let G be an n-vertex
2
graph with exactly n4 edges, where there are no loops or multiple edges (each unordered
pair of distinct vertices is joined by either 0 or 1 edge). An unordered pair of distinct vertices
{x, y} is said to be amicable if they have a common neighbor (there is a vertex z such that
( )
xz and yz are both edges). Prove that G has at least 2 n/2 2 pairs of vertices which are
amicable.
Solution. Define friendship in a different way, bounding below, keeping in mind the
equality case. Then using the previous lemma.

Theorem 6 (Turan’s theorem) — Let G be any graph

with n vertices, such that G is Kr+1 -free. Then G is the
“Turán’s Graph” and is a complete r partite graph. And the
number of edges in G is at most
( )
r − 1 n2 1 n2
· = 1− ·
r 2 r 2
A special case of Turán’s theorem for n = 2 is the Mantel’s
Theorem. It states that the maximal triangle
⌊ ⌋free graph is
n2
a complete bipartite graph with at most edges.
4
Figure 0.1.3: Turán’s Graph

Proof. We need to prove that the maximal graph is the r partite one, and the rest
will follow. We can directly try to prove that this graph is r colorable, but that is
 Graph Theory Counting in Graph 7

quite troublesome. Instead, we try to show that, we can partition the vertices of G
into equivalence classes based on their non-neighbors. Since this is imply the former.
So we need to prove that this holds for this graph.

The way it is done is quite interesting. We need to show that if the criteria doesn’t
hold in this graph, then this graph is not the maximal graph. How are we going to do
that? We compare the degrees of u, w, and replace either u by w or w by u to get a
graph with more edges and without the nasty situation.

Problem 10. 155 birds P1 , P2 , . . . , P155 are sitting down no the boundary of a circle C. Two
birds Pi , Pj are mutually visible if the angle at the center of their cord, m(Pi Pj ) ≤ 10◦ . Find
the smallest number of mutually visible pairs of birds.

Problem 11. For a pair A = (x1 , y1 ) and B = (x2 , y2 ) of points on the coordinate plane,
let d(A, B) = |x1 − x2 | + |y1 − y2 |. We call a pair (A, B) of unordered points harmonic if
1 < d(A, B) ≤ 2. Determine the maximum number of harminc pairs among 100 points in
the plane.

Problem 12 (Swell coloring). Let Kn denote the complete graph on n vertices, that is, the
graph with n vertices’s such that every pair of vertices’s is connected by an edge. A swell
coloring of Kn is an assignment of a color to each of the edges such that the edges of any
triangle are either all of distinct colors or all the same color. Further, more than one color
must be used in total (otherwise trivially if all edges are the same color we √ would have a
swell coloring). Show that if Kn can be swell colored with k colors, then k ≥ n + 1.

Solution. Concentrate on only one vertex.

Problem 13 (Belarus 2001). Given n people, any two are either friends or enemies, and
friendship and enmity are mutual. I want to distribute hats to them, in such a way that
any two friends possess a hat of the same color but no two enemies possess a hat of the
same color. Each person can receive multiple hats. What is the minimum number of colors
required to always guarantee that I can do this?

Solution. In this problem, finding the worst case is a big help, because once the
answer is guessed, the things become really clear.

Problem 14 (ELMO 2017 P5). The edges of K2017 are each labeled with 1, 2 or 3 such that
any triangle has sum of labels at least 5. Determine the minimum possible average of all
labels. (Here K2017 is defined as the complete graph on 2017 vertices’s, with an edge
 Graph Theory Counting in Graph 8

between every pair of vertices’s.)

Solution. A starting idea to get the ans: if we discard of all the 2-edges, we see that
in any triangle, one edge has to be a 3-edge. So... Turan-kinda...

Solution. After getting the ans, and thinking about approaching inductively, if we
remove only one vertex, there will be pairs to consider. But if we remove two ver-
tices, we will only need to consider single vertices after the removal of these two vertices.

Now which pair of vertices are the best choice to remove? Before doing that, lets first
think how much change will we get in the sum after we remove two vertices. Since we
have the ans, we do quick maffs:

m(4m + 1) − (m − 1)(4m − 3) = 8m − 3 = 4 × (2m − 1) + 1

Doesn’t this indicate that we remove a 1-edge, so the other edges coming out of the
two vertices will sum up to be at least 4 ∗ (2m − 1).

Solution. The solution by bern is very pretty. What he probably had thought was:

If we pick a vertex, say u, and take an 1-edge from this vertex to another vertex v, we
see that there are at least as many 3-edges in u than there are 1-edges in v. Now if to
get a more accurate value of d3 (u) (defined naturally), we need to take the maximum
of the values d1 (v) for all v’s connected to u.

Now we need to evaluate the number of 3 edges from the d1 values. Can we put a
bound on this sum? We have this lemma, does this help? Turns out that it does.

What left is to sum it all up to see if we can get the ans.

Problem 15 (ARO 2005 P9.4). 100 people from 50 countries, two from each countries, stay
on a circle. Prove that one may partition them onto 2 groups in such way that neither no
two countrymen, nor three consecutive people on a circle, are in the same group.

Variant: There are 100 people from 25 countries sitting around a circular table. Prove that
they can be separated into four classes, so that no two countrymen are in the same class,
nor any two people sitting adjacent in the circle.

Solution. Thinking of the most natural way of eliminating the consecutive condition
– pair two consecutive verices.
 Graph Theory Counting in Graph 9

Problem 16 (Romanian TST 2012 P4). Prove that a finite simple planar graph has an orien-
tation so that every vertex has out-degree at most 3.

Problem 17 (USA TST 2006 P1). A communications network consisting of some terminals
is called a 3-connector if among any three terminals, some two of them can directly com-
municate with each other. A communications network contains a windmill with n blades if
there exist n pairs of terminals {x1 , y1 }, {x2 , y2 }, . . . , {xn , yn } such that each xi can directly
communicate with the corresponding yi and there is a hub terminal that can directly com-
municate with each of the 2n terminals x1 , y1 , . . . , xn , yn . Determine the minimum value of
f (n), in terms of n, such that a 3 -connector with f (n) terminals always contains a windmill
with n blades.
Solution. Windmills won’t be there if among any 2n + 1 vertices, there were one
vertex that were not connected to any of the other 2n vertices. So that means that we
are dealing Turan-kinda config here. So we can make several ‘compact’ graphs that
are mutually disconnected, and each have at most 2n verices. Guessing from this, the
ans is probably of some form k ∗ 2n + 1. Now we have another condition to consider, 3-
connector. Lets see, if we had 3 disconnected componets, the resulting graph wouldn’t
be a 3-connector. Done...

Problem 18. Graph G on n vertices has the property that the degree of every vertex is greater
than 2. Prove that for every 0 < k < n, there is a simple path with lenght at least n/k or, k
cycles, such that every cycle has at least one node which none of the other cycles has, and
its lenght is not divisible by 3.

Problem 19 (ISL 2005 C4). Let n ≥ 3 be a fixed integer. Each side and each diagonal of
a regular n-gon is labelled with a number from the set {1; 2; ...; r} in a way such that the
following two conditions are fulfilled:
• Each number from the set {1, 2, . . . r} occurs at least once as a label.
• In each triangle formed by three vertices of the n-gon, two of the sides are labelled with
the same number, and this number is greater than the label of the third side.

1. Find the maximal r for which such a labelling is possible.

2. For this maximal value of r, how many such labellings are there?

Solution [Extremal]. Take the edges labeled with r, and delete them. Study what is
left. For the second part, formulate a recursive function, and try out small cases to
find pattern.

Problem 20 (St Petersburg 2020 P11.7). N oligarchs built a country with N cities with
each one of them owning one city. In addition, each oligarch built some roads such that the
 Graph Theory Counting in Graph 10

maximal amount of roads an oligarch can build between two cities is 1 (note that there can
be more than 1 road going through two cities, but they would belong to different oligarchs).
A total of d roads were built. Some oligarchs wanted to create a corporation by combining
their cities and roads so that from any city of the corporation you can go to any city of the
corporation using only corporation roads (roads can go to other cities outside corporation)
but it turned out that no group of less than N oligarchs can create a corporation. What is
the maximal amount that d can have?
Solution. At first I thought about “cuts” where we can only have roads owned by
one oligarch, but it proved to be really complex to work with. So I thought about
constructing the best solution. Trying it out for 3, 4 immediately gave the idea to
construct optimally. Now on forward to proving it.

The proof is roughly as followed. We will

(N ) show that if we remove the oligarch indexed
N , then we need to remove at most 2 roads. Since there is no road owned by N
that connects to city N , the roads owned by N forms a forest of graphs with the other
cities.

We show that for every edge in that forest, there is one less road leaving city N . Which
we do by induction. We take the set {1, 2, . . . N − 1}, one of these cities has no road
with N . WLOG, it is 1. Then inductively we can assume that city i can have at most
i − 1 roads with N .

Now for each i, starting with N − 1, and ending at 1, we show that in reality, i can
have at most i − 1 − VN (i) where VN (i) is the number of roads owned by N leaving i.
It works inductively, and so after it, we can just remove N , and assume our inductive
hypothisis. Which gives us our answer of
( )
N
3
 Graph Theory Algorithms in Graph 11

0.1.2 Algorithms in Graph

Definition (Cut)— A cut is a partition of the

vertices of a graph into two disjoint subsets.
Any cut determines a cut-set, the set of edges
that have one endpoint in each subset of the
partition. These edges are said to cross the
cut. In a connected graph, each cut-set de-
termines a unique cut, and in some cases cuts
are identified with their cut-sets rather than
(a) Minimum Cut (b) Maximum Cut
with their vertex partitions.

2
Theorem 7 (Prufer sequence) — Consider a la- 1

beled tree T with vertices’s {1, 2, ..., n}. At step i, 3

remove the leaf with the smallest label and set the 4

ith element of the Prüfer sequence to be the label of

this leaf’s neighbour. Prove that a Prüfer sequence of 5

length n − 2 defines a Tree with length n. 6

Figure 0.1.4: 4, 4, 4, 5

Problem 21 (German TST 2004 E7P3). We consider graphs with vertices colored black or
white. “Switching” a vertex means: coloring it black if it was formerly white, and coloring
it white if it was formerly black.
Consider a finite graph with all vertices colored white. Now, we can do the following
operation: Switch a vertex and simultaneously switch all of its neighbours (i.e. all vertices
connected to this vertex by an edge). Can we, just by performing this operation several
times, obtain a graph with all vertices colored black?

Solution. A classical example of creating complex moves from counter cases.

Problem 22 (ARO 2014 P9.8). In a country of n cities, an express train runs both ways
between any two cities. For any train, ticket prices either direction are equal, but for any
different routes these prices are different. Prove that the traveler can select the starting
city, leave it and go on, successively, n − 1 trains, such that each fare is smaller than that
of the previous fare. (A traveler can enter the same city several times.)

Problem 23 (Generalization of ARO 2014 P9.8). Let A be a set of n points in the space.
From the family of all segments with endpoints in A , q segments have been selected and
 Graph Theory Algorithms in Graph 12

colored yellow. Suppose that all yellow segments are of different length. Prove that there
exists a polygonal line composed of m yellow segments, where m ≥ 2q n , arranged in order of
increasing length.

Solution. There are no local information given that we can use to consturct a way,
so our only bet is to try some global approach. We want at least one path of length
more than n − 1, and there are a total of n(n−1)
2 edges. So either we want to partition
the edges in 2n paths, or we count each edge twice and then partition then in n paths,
giving us our desired result.

We figure out the second approach works. So we want to find n paths that begin at
each of the n vertices and cover all the edges twice. This idea soon lead us to the
magical solution:

Let one traveller go to each of the n cities. Then we select the costliest train and swap
the two travellers on its two ends. We keep doing this until all the trains have been
used.

This works because every traveller follows a path of gradually decreasing train cost,
and every edge is used exactly twice.

Solution [ninjaturtle]. Consider the direct graph where each edge has two directions
(2q edges). A directed edge e is called terminal if there isn’t an edge f with larger
value such that the end vertex of e is the same as the start vertex of f .

At step i, we remove all terminal edges in the remaining graph. If we can show that
each step removes at most n direct edges, then 2q/n steps are required to remove all
edges, implying there exists a polygonal line of increasing length of length at least 2q/n.

Let Ii (a), Oi (a) be the in-degree and out-degree of a before step i. Assume we are at
the time before step k. Put m = Ok (a), and let e be the outgoing edge of a with the
largest value v. Then v ≥ m. After step k, only incoming edges of a with value ≥ m
will have possibly been removed. Thus Ik+1 (a) ≥ m − 1 = Ok (a) − 1. Sum it over all a

#edges before step k+1 = ∑ Ik+1 (a) ≥ ∑ Ok (a) − n = #edges before step k
a a

and we have shown the number of edges after each step decreases by at most n.

Problem 24. Given a bipartite graph, prove that the minimum number of colors required to
color the edges of the graph such that no node is adjacent to 2 edges of same color is the
maximum degree of the graph.
 Graph Theory Algorithms in Graph 13

Problem 25. For every bipartite

⌈ graph
⌉ prove that it’s edges can be bicolored so that each
deg
node is adjacent to atmost edges of any color.
2

Solution. Using the main property of a bipartite graph.

Solution. After finding the cycle solution, to optimize it, we recall that we can find
a Eulerian Path (if it exists) in O(V + E). Now we want to make the graph have a
Eulerian path, so we add a vertice to both sides of the graph, and join them with odd
vertices from the other side.

Problem 26 (Turkey National MO 2002 P3). Graph Airlines (GA) operates flights between
some of the cities of the Republic of Graphia. There are at least three GA flights from each
city, and it is possible to travel from any city in Graphia to any city in Graphia using GA
flights. GA decides to discontinue some of its flights. Show that this can be done in such
a way that it is still possible to travel between any two cities using GA flights, yet at least
2/9 of the cities have only one flight.
Simplified: In a connected graph, every vertex has degree at least 3. Prove that some edges
can be deleted to turn that graph into a tree with at least 29 leaves.
1
Better Approximation: We can actually achieve 4 with careful construction.

Solution [dgrozev]. First we construct a spanning tree T that maximizes the number of
leaves, then we bound the number. We define G(V, E), n = |V | with the usual notations.

Let f : V → V . We initialize the tree by selecting a vertex v by random, and adding it

to T . We inductively add the vertices according to the following priority checks:

1. If there is a vertex v ̸∈ T that is connected to u ∈ T such that u is not a leaf,

then add v, uv to T .

2. If u ∈ T is a leaf and there are two v1 , v2 not in T that are connected to u, add
v1 , v2 and uv1 , uv2 to T .

3. If u ∈ T is a leaf, and there is a v which has two neighbors outside of T , then

add v, uv to T , and let f (u) = v.

4. If u ∈ T is a leaf, there is a v ̸∈ T which is connected to at most one vertex outside

T , and connected to u′ ∈ T , then add v, uv to T and let f (u) = u′ .

This algorithm will add all the vertices to the tree. We now need to bound the number
of leaves.
 Graph Theory Algorithms in Graph 14

Let n1 , n2 , n3 be the set of vertices that have 1, 2 and more than 3 neighbors respectively.
Since f is a injection from the set n2 to either n1 or n3 , we have since n = n1 + n2 + n3 ,
n
n2 ≤ n1 + n3 , n2 ≤
2
Bounding the number of edges gives us:

2n − 2 ≥ n1 + 2n2 + 3n3
= n1 + 3(n − n1 ) − n2
n
≥ 3n − 2n1 −
2
n
=⇒ n1 ≥ + 1
4

Solution [Paper]. The construction is the same as before. But we define a different
cost fuction f to bound our leaves count. Let D(T ) be the number of leaves in T which
doesn’t have a neighbor outside of T . Let L(T ) be the number of all leaves, and V (T )
is the number of vertices of T . Then consider

f (T ) = 3L(T ) + D(T ) −V (T )

We show that f (T ) is non decreasing in our construction. If it is, we will get by setting
f (T0 ) for a one vertex and its neighbor tree T0 ,

f (T ) ≥ f (T0 ) ≥ 3 × 3 + 0 − 4 = 5

And since D(T ′ ) = L(T ′ ) for a spanning tree T ′ ,

N +5
L(T ′ ) ≥
4
We now check that for all of your steps in construction, f (T ) is non decreasing.

Problem 27 (ISL 2005 C1). A house has an even number of lamps distributed among its
rooms in such a way that there are at least three lamps in every room. Each lamp shares a
switch with exactly one other lamp, not necessarily from the same room. Each change in
the switch shared by two lamps changes their states simultaneously. Prove that for every
initial state of the lamps there exists a sequence of changes in some of the switches at the
end of which each room contains lamps which are on as well as lamps which are off.

Problem 28 (ISL 2013 C3). A crazy physicist discovered a new kind of particle which he
called an i -mon, after some of them mysteriously appeared in his lab. Some pairs of i
-mons in the lab can be entangled, and each i -mon can participate in many entanglement
 Graph Theory Algorithms in Graph 15

relations. The physicist has found a way to perform the following two kinds of operations
with these particles, one operation at a time.

1. If some i -mon is entangled with an odd number of other i -mons in the lab, then the
physicist can destroy it.

2. At any moment, he may double the whole family of i -mons in the lab by creating
a copy I ′ of each i -mon I . During this procedure, the two copies I ′ and J ′ become
entangled if and only if the original i -mons I and J are entangled, and each copy
I ′ becomes entangled with its original i -mon I ; no other entanglements occur or
disappear at this moment.

Prove that the physicist may apply a sequence of much operations resulting in a family of
i -mons, no two of which are entangled.

Solution. As there are an integer number of i -mons, it is quite natural to use

induction. We try to find an algorithm to reduce the number of particles.
Another way to do this is to consider the chromatic number of the graph. If we can
show that this number reduces after some move, then we are done by induction.

Problem 29 (ISL 2005 C2). A forest consists of rooted (i. e. oriented) trees. Each vertex
of the forest is either a leaf or has two successors. A vertex v is called an extended successor
of a vertex u if there is a chain of vertices’s u0 = u, u1 , u2 . . . ut−1 , ut = v with t > 0 such that
the vertex ui+1 is a successor of the vertex ui for every integer i with 0 ≤ i ≤ t − 1.

Let k be a nonnegative integer. A vertex is called dynastic if it has two successors and each
of these successors has at least k extended successors.

n
Prove that if the forest has n vertices, then there are at most k+2 dynastic vertices.

Solution. Trying to apply induction, we realize the bound is very loosy. That’s why
when we try to add in the inductive step, the value becomes larger than the bound. To
stop that overflow, we tighten the bound.

Solution. The second and dummy approach is to first doing some smaller cases, finding
small infos, taking the root, seeing that the bound doesnt work, but it would work if
one of the successors of the root would have exactly or less than 2k + 3 successors. As
we can’t always guarantee that, we look for such a vertex with 2k + 3 successors. We
do some work with it and by induction its done.
 Graph Theory Algorithms in Graph 16

Problem 30 (All Russia 2017 9.1). In a country some cities are connected by oneway
flights (There are no more then one flight between two cities). City A called ”available” for
city B , if there is flight from B to A , maybe with some transfers. It is known, that for
every 2 cities P and Q exist city R , such that P and Q are available from R. Prove, that
exist city A , such that every city is available for A.

Problem 31 (Jacob Tsimerman Induction). There are 2010 ninjas in the village of Konoha
(what? Ninjas are cool.) Certain ninjas are friends, but it is known that there do not exist
3 ninjas such that they are all pairwise friends. Find the maximum possible number of pairs
of friends.(If ninja A is friends with ninja B , then ninja B is also friends with ninja A.)

Problem 32 (USA TST 2011 D3P2). Let n ≥ 1 be an integer, and let S be a set of integer
pairs (a, b) with 1 ≤ a < b ≤ 2n . Assume |S| > n · 2n+1 . Prove that there exists four integers
a < b < c < d such that S contains all three pairs (a, c), (b, d) and (a, d).

Solution. Using Induction to the first and last half of the set S shows us the hardest
part of the problem. Then ordering the left and right elements with some sort of
hierarchy is all the work left to do.

Problem 33 (ISL 2016 C6). There are n ≥ 3 islands in a city. Initially, the ferry company
offers some routes between some pairs of islands so that it is impossible to divide the islands
into two groups such that no two islands in different groups are connected by a ferry route.

After each year, the ferry company will close a ferry route between some two islands X
and Y . At the same time, in order to maintain its service, the company will open new
routes according to the following rule: for any island which is connected to a ferry route
to exactly one of X and Y , a new route between this island and the other of X and Y is added.

Suppose at any moment, if we partition all islands into two nonempty groups in any way,
then it is known that the ferry company will close a certain route connecting two islands
from the two groups after some years. Prove that after some years there will be an island
which is connected to all other islands by ferry routes.

Solution. It is only natural to use induction on this kinda problems. After some trying,
we see that if we remove 1 node, We get to nowhere, but if we remove 2 nodes, we
get something interesting. So now focus on those two nodes and the rest of the nodes
separately. Its not hard from there.
 Graph Theory Algorithms in Graph 17

Solution. As it seems, the separation of the graph was the main observation. We can
call this trick Bringing Order in the Chaos.

Problem 34 (ARO 2013 P9.5). 2n real numbers with a positive sum are aligned in a circle.
For each of the numbers, we can see there are two sets of n numbers such that this number
is on the end. Prove that at least one of the numbers has a positive sum for both of these
two sets.
Solution. Since there is nothing specfic about the sum, we may safely assume that it
is 0, because (1) probably it works, and (2) it makes things more convenient. How we
do that? we decrease every number by the average.

Now, Consider every block of n consecutive blockes of numbers. When are two blocks
connected? When they share the same end. What if we consider them as vertices, and
this “connectivity” as edges? We see that cycles pop out.

And we make use of the fact that our sum is 0. So signs are sure to bet flipped at the
opposite side, and there are odd and even -ness in cycles that we can use.

Problem 35 (USA TST 2011 P2). In the nation of Onewaynia, certain pairs of cities are
connected by roads. Every road connects exactly two cities (roads are allowed to cross each
other, e.g., via bridges). Some roads have a traffic capacity of 1 unit and other roads have
a traffic capacity of 2 units. However, on every road, traffic is only allowed to travel in one
direction. It is known that for every city, the sum of the capacities of the roads connected
to it is always odd. The transportation minister needs to assign a direction to every road.
Prove that he can do it in such a way that for every city, the difference between the sum of
the capacities of roads entering the city and the sum of the capacities of roads leaving the
city is always exactly one.

Solution. As there are two types of subgraph, 1 -type and 2 -type. By some work-
arounds, we see that we have to work distinctly in both types of graphs. Firstly, if we
work in type- 1 , we see after making a path from node x, y , the degrees of x, y will be
{1, −1} and the degrees of other nodes on the path will be the same. After that, we
make every nodes have degree either {1, −1}. So after this operation we remove the
1 -edges. Now, when dealing with the type- 2 sub-graph. Start over from zero, we see
that when making a path between nodes x, y the degree of those two changes parity,
and other nodes on the path stays the same. So select two odd nodes....

Solution. Dealing with two different kind of edges simultaneously is messy, so we

work with graph 1 and graph 2 differently. Now on both graphs, we can remove cycles.
And in graph 2 , we see that we can remove any big paths if there is a edge 1 joining
the two endpoints. Since if the new graph works then the previous graph works too.
 Graph Theory Algorithms in Graph 18

[Several cases to show here] And if there is no edge joining the two endpoints, replace
the path by joining the two endpoints by a edge 2.

Now there are only edge 1 s, and lone edge 2 s. Now dividing the graph 1 into paths
of edge 1 , and dealing with several small cases, we are done.

Problem 36 (Iran TST 2009 P6). We have a closed path that goes from one vertex to
another neighboring vertex, on the vertices of a n × n square which pass throgugh each
vertex exactly once. Prove that we have two adjacent vertices such that if we cut the path
at these two points then the length of each open paths is at least n2 /4.

Solution [grobber]. After drawing the closed path we notice that it divides the grid
into a tree like structure, which we definitely need to explore!

After drawing the tree with the unit squares as vertices, we try to reformulate our
problem in our new tree. We want to find an edge of this tree that will divide the tree
2
into two parts, and those two part should have perimeter more than n4 .

We know of Pick’s Theorem which lets us relate area with perimiter of such polygons.
Which we use to do some bounding. We also need to show that if every vertex in a
tree has degree at most 4, then there is an edge that divides the tree into two “big”
portions, which we will use.

Problem 37 (Iran TST 2006). Suppose we have a simple polygon (that is it does not in-
tersect itself, but not necessarily convex). Show that this polygon has a diagonal which is
completely inside the polygon and the two arcs it creates on the polygon perimeter (the two
arcs have 2 vertices in common) both have at least one third of the vertices of the polygon.

Solution [grobber]. First we triangulate the polygon. Now we take the diagonal that
divides the polygon into two arcs whose difference in length is the least. We show that
it satisfies the requirement.

Solution [induction]. After the triangulation, we can also do induction on the number
of triangles, by removing a “outer” triangle.

Solution [graph transformation]. We can convert the problem into a graph by con-
sidering the triangles as vertices and joining two vertices if they share a common side.
Then this graph is a tree of which all vertices have degree at most 3. And we know
that in any graph with maximum degree 3, there is way to remove an edge to divide
the graph into two subgraphs with at least n3 vertices.
 Graph Theory Algorithms in Graph 19

Problem 38 (OC Chap2 P2). Arutyun and Amayak perform a magic trick as follows. A
spectator writes down on a board a sequence of N (decimal) digits. Amayak covers two
adjacent digits by a black disc. Then Arutyun comes and says both closed digits (and their
order). For which minimal N can this trick always work? NOTE: Arutyun and Amayak have
a strategy determined beforehand.

Solution. We have to actually find a bijection between all of the combinations the
spectator can create, and all of the combinations that Arutyun might see when he
comes back. Which tells us to use “Perfect Matching” tricks.

Solution [Existence]. For this trick to always work, they have to make a bijection from
a set of N digits with two covered, to an unique set of N digits. Consider a bijection
from the set of 0 − 9 strings with length N to the set of 0 − 9 strings with length N
with 2 adjacent digits unknown. There exist a bijection iff the two sets satisfy Hall’s
Marriage Theorem. By double counting we get the value of N from here.

Problem 39 (Simurgh 2019 P3). Call a graph symmetric, if one can put its vertices on the
plane such that it becomes symmetric wrt a line (which doesn’t pass through any vertex).
Find the minimum value of k such that (the edges of) every graph on 100 vertices, can be
decomposed into k symmetric subgraph.

Problem 40 (RMM 2020 P3). Let n ≥ 3 be an integer. In a country there are n airports and
n airlines operating two-way flights. For each airline, there is an odd integer m ≥ 3, and m
distinct airports c1 , . . . , cm , where the flights offered by the airline are exactly those between
the following pairs of airports: c1 and c2 ; c2 and c3 ; . . . ; cm−1 and cm ; cm and c1 .
Prove that there is a closed route consisting of an odd number of flights where no two
flights are operated by the same airline.

Solution [Weird Induction]. Fix one vertice, merge all neighbors with it that has a
unique airline between them.

Solution [Element of Time]. Add one edge from each cycle one at a time, without
creating a cycle. Our objective is to show that when we reach the maximum stage
where one edge creates a cycle, that cycle is of odd length.