An undirected graph with $n$ vertices has the property that if vertices $a,b,c$ have no edges between them, then there exists a vertex $d$ that has an edge to at least two of $a,b,c$. What is the minimum possible maximum degree in this graph?
One possibility of such a graph is to divide the vertices into two groups with $n/2$ vertices (assuming $n$ is even) and have each group be a clique. In this graph, the maximum degree is $n/2-1$. If we let the graph be composed of three cliques, the property is no longer satisfied.