Require Proof
Difference between en1 and en2, changed 57 character(s)
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 
iI can't prove that dividpartitioning all n vertices into aone complete graph and then removing some unnecessary edges is not more optimal than this. Please help me ToT.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English MathK30 2024-03-15 07:54:17 57
en1 English MathK30 2024-03-15 07:46:39 415 Initial revision (published)