MathDB
Simple graph

Source: IMS 2014 - Day2 - Problem9

October 4, 2014
geometrygeometric transformationgraph theorycombinatorics proposedcombinatorics

Problem Statement

Let GG be a 2n−2n-vertices simple graph such that in any partition of the set of vertices of GG into two n−n-vertices sets V1V_1 and V2V_2, the number of edges from a vertex in V1V_1 to another vertex in V1V_1 is equal to the number of edges from a vertex in V2V_2 to another vertex in V2V_2. Prove that all the vertices have equal degrees.
Back to ProblemsView on AoPS