MathDB

The minimum number of edges of G is (7n^2- 3n)/2

Source: China TST 2011 - Quiz 3 - D1 - P3

May 20, 2011

algorithmcombinatorics unsolvedcombinatorics

Problem Statement

Let

G

be a simple graph with

3n^2

vertices (

n\geq 2

). It is known that the degree of each vertex of

G

is not greater than

4n

, there exists at least a vertex of degree one, and between any two vertices, there is a path of length

\leq 3

. Prove that the minimum number of edges that

G

might have is equal to

\frac{(7n^2- 3n)}{2}