MathLabs

Problem 3

Let nn be a positive integer. nn people take part in a party. For each pair, either the two people are acquainted or they are not. What is the maximum possible number of pairs that are not acquainted but have a common acquaintance among the participants?
Step 4 of 6: Connected graph bound
Previous stepNext step
e(G)≥n−1e(G)\ge n-1
Detailed analysis

Every connected graph on nn vertices has at least n−1n-1 edges.