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.

  • $\begingroup$ You have shown that such a graph can have at most two connected components, and if it does, then each of these must be a complete graph. In that case, the minimum maximum degree is $\lceil n/2\rceil-1.$ So it remains to consider a connected graph. A complete bipartite graph has the required property, and if the bipartition sets are $\{u_1,\dots, u_k \}$ and $\{v_1,\dots, v_k \},$ we can delete the edges $u_jv_j, j=1,\dots,k$ to get the same maximum degree. I haven't been able to show that this is the minimum, though. I feel that you've got the answer, but I can't prove it. $\endgroup$
    – saulspatz
    Mar 24, 2018 at 12:48
  • 1
    $\begingroup$ You can do better than $n/2$. Taking the $n/6$th-power of a cycle gives $n/3$, approximately. Still not sure if this is optimal. $\endgroup$ Mar 24, 2018 at 19:46


You must log in to answer this question.

Browse other questions tagged .