A simple graph has 200000 edges and for any 3 vertices at least one of the edges is not present in What is the least number of vertices that can have?
Details and assumptions
A simple graph does not have multiple edges between vertices, or self loops.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Consider a graph H that has n vertices, for any 3 vertices at least one of the edges amongst them is missing, and has the maximal number of edges. Consider two vertices a , b that are not adjacent in H . Let A be the neighbours of a and B be the neighbours of b . There cannot be any edges between vertices of A , since this would violate our condition, and similarly there are no edges between vertices of B . Since H has the maximal number of edges, we must have ∣ A ∣ = ∣ B ∣ , since otherwise we could find a graph with a larger number of edges. We can let b have neighbour set A and get a new graph that still has a maximal number of edges. We can repeat this process for every vertex that is not adjacent to a , and we have now divided our graph into two parts, the set A which has no edges between vertices, and the set V ( H ) − A which also has no edges between vertices. For any vertex c ∈ A and d ∈ A , the edge c d is present, so the number of edges in H is ∣ A ∣ × ( n − ∣ A ∣ ) . We know this is maximized when ∣ A ∣ = ⌊ 2 n ⌋ and n − ∣ A ∣ = ⌈ 2 n ⌉ (or vice versa). Thus, the maximal number of edges is ⌊ 2 n ⌋ ⌈ 2 n ⌉ . We have 4 4 7 × 4 4 7 = 1 9 9 8 0 9 , so a graph with the desired property on 894 vertices can have a maximum of 199809 edges. We also have 4 4 7 × 4 4 8 = 2 0 0 2 5 6 , so n = 8 9 5 is the least number of vertices that G could have.