MathDB

1

Part of 1993 Iran MO (2nd round)

Problems(1)

Minimum number of edges [Iran Second Round 1993]

Source:

11/25/2010
GG is a graph with nn vertices A1,A2,…,An,A_1,A_2,\ldots,A_n, such that for each pair of non adjacent vertices AiA_i and AjA_j , there exist another vertex AkA_k that is adjacent to both AiA_i and Aj.A_j .
(a) Find the minimum number of edges in such a graph.
(b) If n=6n = 6 and A1,A2,A3,A4,A5,A_1,A_2,A_3,A_4,A_5, and A6A_6 form a cycle of length 6,6, find the number of edges that must be added to this cycle such that the above condition holds.
combinatorics proposedcombinatorics