MathDB

In a country, there are some cities and the city named Ben Song is capital. Each cities are connected with others by some two-way roads. One day, the King want to choose

n

cities to add up with Ben Song city to establish an expanded capital such that the two following condition are satisfied:
(i) With every two cities in expanded capital, we can always find a road connecting them and this road just belongs to the cities of expanded capital.
(ii) There are exactly

k

cities which do not belong to expanded capital have the direct road to at least one city of expanded capital.
Prove that there are at most

\binom{n+k}{k}

options to expand the capital for the King.

Problem Statement