MathDB
Minimum possible number of edges in the graph

Source: Japan Mathematical Olympiad Finals 1997 , Problem 3

March 23, 2006
ceiling functioncombinatorics proposedcombinatorics

Problem Statement

Call the Graph the set which composed of several vertices P1, ⋯P2P_1,\ \cdots P_2 and several edges ((segments)) connecting two points among these vertices. Now let GG be a graph with 9 vertices and satisfies the following condition.
Condition: Even if we select any five points from the vertices in G,G, there exist at least two edges whose endpoints are included in the set of 5 points.
What is the minimum possible numbers of edges satisfying the condition?
Back to ProblemsView on AoPS