MathDB
Graph Theory

Source: 2003 National High School Mathematics League, Exam Two, Problem 3

March 16, 2020
graph theory

Problem Statement

A space figure is consisted of nn vertexes and ll lines connecting these vertices, where n=q2+q+1,l≥12q(q+1)2+1,q≥2,q∈Z+n=q^2+q+1, l\geq\frac{1}{2}q(q+1)^2+1,q\geq2,q\in\mathbb{Z}_+. The figure satisfies: every four vertices are not coplane, every vertex is connected by at least one line, and there is a vertex connected by at least q+2q+2 lines. Prove that there exists a space quadrilateral in the figure. Note: a space quadrilateral is figure with four vertices A,B,C,DA, B, C, D and four lines AB,BC,CD,DA AB, BC, CD, DA.
Back to ProblemsView on AoPS