Hi Guys.

I meet a problem which we have to build a graph of n vertices such that the number of edges is minimized and among 3 vertices i j k, we have a least one of the edge i j, i k, or k j.

I think the solution would be to create 2 complete graphs, each with n / 2 vertices. But I can't prove that partitioning all n vertices into one complete graph and then removing some unnecessary edges is not more optimal than this. Please help me ToT.