MathDB
Simple connected graph with 100 vertices and 2013 edges

Source: Turkey National Olympiad Second Round 2013 P3

November 28, 2013
graph theorycombinatoricsGraph coloringConnected graphs

Problem Statement

Let GG be a simple, undirected, connected graph with 100100 vertices and 20132013 edges. It is given that there exist two vertices AA and BB such that it is not possible to reach AA from BB using one or two edges. We color all edges using nn colors, such that for all pairs of vertices, there exists a way connecting them with a single color. Find the maximum value of nn.
Back to ProblemsView on AoPS