Hi Guys.
I meet a problem which we have to build a graph of n vertices such that the number of edges is minimized and among 3 vertices i j k, we have a least one of the edge i j, i k, or k j.
I think the solution would be to create 2 complete graphs, each with n / 2 vertices. But I can't prove that partitioning all n vertices into one complete graph and then removing some unnecessary edges is not more optimal than this. Please help me ToT.
Auto comment: topic has been updated by MathK30 (previous revision, new revision, compare).
Hello lady/bro, by taking the complement of this graph, we reduce it to the Turan's theorem, and the answer is $$$\frac{n(n-1)}{2} - \lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil$$$. You can construct the graph by induction.
tk u bro
can you tell me the application of turan theorem to this problem :>
The complement of your desired graph is $$$T_{n, 2}$$$.
and then we have a complete graph all right
Your graph is the complete graph $$$K_n$$$ ($$$\frac{n(n-1)}{2}$$$ edges) minus $$$T_{n, 2}$$$ ($$$\lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil$$$ edges).
ok thank you, it means lot :>
:>
isn't it negative for n = 4 ?? but answer is 3
i was getting ((n-1)(n-2))/2. is it right ??
for n = 4 answer will be 2 bro
wait why does this work?