Minimum number of edges [Iran Second Round 1993]
Source:
November 25, 2010
combinatorics proposedcombinatorics
Problem Statement
is a graph with vertices such that for each pair of non adjacent vertices and , there exist another vertex that is adjacent
to both and (a) Find the minimum number of edges in such a graph.(b) If and and form a cycle of length find the number of edges that must be added to this cycle such that the above condition holds.