\(P_3\)-Connected Graphs of Minimum Size

A graph without \(4\)-cycles is called \(C_4\)-free. A \(C_4\)-free graph is \(C_4\)-saturated if adding any edge creates a 4-cycle. Ollmann showed that any \(n\)-node \(C_4\)-saturated graph has at least \(\frac{3}{2}n – 3\) edges. He also described the set of all \(n\)-node \(C_4\)-saturated graphs with \(\lceil \frac{3}{2}n \rceil – 3\) edges. A graph is \(P_3\)-connected if each pair of nonadjacent nodes is connected by a path with exactly \(3\) edges. A \(C_4\)-saturated graph is \(P_3\)-connected, but not vice versa. We generalize Ollmann’s results by proving that any \(n\)-node \(P_3\)-connected graph has at least \(\frac{3}{2}n – 3\) edges. We also describe the set of all \(n\)-node \(P_3\)-connected graphs with \(\lceil \frac{3}{2}n \rceil – 3\) edges. This is a superset of Ollmann’s set as some \(n\)-node \(P_3\)-connected graphs with \(\lceil \frac{3}{2}n \rceil – 3\) edges do have \(4\)-cycles.