2
$\begingroup$

A connected undirected graph with $n\geq 4$ vertices has the property that for any two vertices linked by an edge, there exist two other vertices such that every pair of the four vertices is linked by an edge. What is the minimum number of edges in this graph?

A simple way to satisfy this property is to make cliques of size four (with remainder vertices joining one of the cliques), giving about $3n/2$ edges, but the problem is that the graph is not connected. If we try to make the graph connected, we can fix three vertices and join them to all other vertices (and to each other). This gives $3n-6$ edges in total.

$\endgroup$
1
$\begingroup$

We can be a bit more efficient than that, adding cliques of three new vertices and one old vertex. This gives $2n-2$ edges if $n\equiv 1\mod 3$, and that's best possible.

When we add a new vertex, it must be part of a size-4 clique. We also add all the vertices in that clique at the same time. That clique must share at least one vertex with what we already had to remain connected. With one vertex shared, we add $3$ vertices and $6$ edges. With two vertices shared, we add $2$ vertices and $\ge 5$ edges. With three vertices shared, we add $1$ vertex and $\ge 3$ edges. Clearly, the first option of three vertices at a time is most efficient.

Of course, starting at a $K_4$, we can't reach all values of $n$ without using the other options at least a little.
For $n=5$, we'll need to add a clique sharing three old vertices. Make those part of a clique and we add three edges, for $9$ edges, one more than the unattainable $2n-2$. From there, adding three vertices at a time will let us handle $n$ vertices in $2n-1$ edges if $n\equiv 2\mod 3$.
For $n=6$, we add a clique sharing two vertices with the first clique. The added five edges give us a total of $11$, one more than the unattainable $2n-2$. From there, adding three vertices at a time will let us handle $n$ vertices in $2n-1$ edges if $n\equiv 0\mod 3$.

So there's the answer: the minimum number of edges $f(n)$ required for $n\ge 4$ is $$f(n)=\begin{cases}2n-2&n\equiv 1\mod 3\\2n-1&\text{otherwise}\end{cases}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.