MathDB
Iran TST P9

Source: Iranian TST 2022 problem 9

April 2, 2022
graph theoryTreescombinatorics

Problem Statement

consider n≥6n\geq 6 points x1,x2,…,xnx_1,x_2,\dots,x_n on the plane such that no three of them are colinear. We call graph with vertices x1,x2,…,xnx_1,x_2,\dots,x_n a "road network" if it is connected, each edge is a line segment, and no two edges intersect each other at points other than the vertices. Prove that there are three road networks G1,G2,G3G_1,G_2,G_3 such that GiG_i and GjG_j don't have a common edge for 1≤i,j≤31\leq i,j\leq 3.
Proposed by Morteza Saghafian
Back to ProblemsView on AoPS