Size in maximal triangle-free graphs and minimal graphs of diameter 2 (Q1842148): Difference between revisions

The authors study triangle-free graphs which are maximal in the sense that the addition of any edge creates a triangle. They show that a maximal triangle-free graph with \(n\geq 5\) vertices is either a complete bipartite graph or has a number \(e\) of edges with \(2n- 5\leq e\leq \left\lfloor{1\over 4} (n- 1)^ 2\right\rfloor+ 1\), and construct an example for each of these possible edge-numbers. They also study graphs of diameter 2 which are minimal in the sense that the deletion of any edge increases the diameter. A triangle-free graph is minimal of diameter 2 if and only if it is maximal triangle-free. Using a result of Füredi that for \(n> n_ 0\) a nonbipartite minimal diameter-2 graph has at most \(\left\lfloor{1\over 4} (n- 1)^ 2\right\rfloor+ 1\) edges, they show that for \(n> n_ 0\) a non-bipartite \(n\)-vertex \(e\)-edge minimal diameter-2 graph exists if and only if \(2n- 5\leq e\leq \left\lfloor{1\over 4}(n- 1)^ 2\right\rfloor+ 1\). There is a 6-vertex 8-edge nonbipartite minimal diameter-2 graph, so \(n_ 0\geq 6\).