MathDB
Connected graph

Source: Iranian 3rd round Combinatorics exam P1 - 2014

September 25, 2014
combinatorics proposedcombinatorics

Problem Statement

Denote by gng_n the number of connected graphs of degree nn whose vertices are labeled with numbers 1,2,...,n1,2,...,n. Prove that gn≥(12).2n(n−1)2g_n \ge (\frac{1}{2}).2^{\frac{n(n-1)}{2}}. Note:If you prove that for c<12c < \frac{1}{2}, gn≥c.2n(n−1)2g_n \ge c.2^{\frac{n(n-1)}{2}}, you will earn some point!
proposed by Seyed Reza Hosseini and Mohammad Amin Ghiasi
Back to ProblemsView on AoPS