Edges in a graph with no triangles
Discrete Mathematics
Level
5
A simple graph \(G\) has 200000 edges and for any 3 vertices \(v,w,x,\) at least one of the edges \(vw, wx, xv\) is not present in \(G.\) What is the least number of vertices that \(G\) can have?
Details and assumptions
A simple graph does not have multiple edges between vertices, or self loops.
by
Calvin Lin