MathK30's blog

Require Proof
By MathK30, history, 9 months ago, In English

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.

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by MathK30 (previous revision, new revision, compare).

→ Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    tk u bro

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you tell me the application of turan theorem to this problem :>

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The complement of your desired graph is $$$T_{n, 2}$$$.

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        and then we have a complete graph all right

        → Reply
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          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).

          → Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    isn't it negative for n = 4 ?? but answer is 3

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    wait why does this work?

    → Reply