A graph with $40$ vertices is given. It is known that among any $5$ vertices there is one connected to the other 4.What is the minimum possible number of edges in this graph?
Proof: consider a group of $3$ vertices. Let them be pairwise unrelated, then:
-
Any two vertexes that complement the group up to $5$ must be connected (otherwise, there will not be at least $1$ among the $5$ vertexes that is connected to the other $4$).
-
There can be only $1$ vertex that is not connected to any of the three initially considered pairwise unrelated vertices (otherwise, there is not at least $1$ vertex that is connected to the other $4$).
Thus, all vertexes except $4$ must be pairwise connected. Therefore, the minimum number of edges in this case is equal to $780-6=774$. Now let's assume that this is not the minimum number of edges. Then among any $3$ vertices there is at least $1$ vertex connected to another vertex from this group of $3$. But then the maximum number of edges that can be unconnected in this graph is $40/2=20$. (otherwise, there are $3$ pairwise unconnected vertices).
Therefore, the minimum number of edges is $780-20=760$. Answer: $760$.
Is my proof correct?
Best Answer
Your analysis of the second case is wrong: it's possible to have much fewer than $760$ edges, and still avoid the three pairwise non-adjacent vertices of your first case. For example, you could split the vertices into two groups of $20$, and connect all the vertices in each group. (Of course, that doesn't satisfy the other conditions in the problem...)
As an aside, you should avoid using the word "connected" to talk about vertices with an edge between them, since it's ambiguous: it can also refer to connected components. Use "adjacent" instead.
It's possible to avoid this problem if we split up the cases in a different way:
Case 1. There exist three vertices $u,v,w$ such that at most one of the edges $uv$, $uw$, $vw$ is present.
This case is handled in the same way as your first case. If we take any two vertices $x,y$, then $\{u,v,w,x,y\}$ has to have a vertex adjacent to all the other $4$. This must be either $x$ or $y$. So the other $37$ vertices are all adjacent, and all of them except at most one are adjacent to all three of $u,v,w$.
This leaves at most $6$ possible missing edges, and so the graph has at least $774$ edges.
Case 2. For any three vertices $u,v,w$, at least two of the edges $uv, uw, vw$ are present.
In the complement of our graph, for any three vertices $u,v,w$, at most one edge is present between them. In particular, in the complement, no vertex can have degree $2$ or more. This means that the complement can have at most $20$ edges (since the sum of degrees is at most $40$) and so our graph has at least $760$ edges.
We are still not done! We need to prove that such a graph is possible. Here's a graph that works: name the vertices $u_1, u_2, \dots, u_{20}$ and $v_1, v_2, \dots, v_{20}$, then include every edge except the $20$ edges $u_1v_1, u_2v_2, \dots, u_{20}v_{20}$. It can be checked, and you should check this, that this graph satisfies the condition in the problem, no matter how we choose $5$ vertices from it.