I am supposed to decide, if the statement is true or false and use arguments for my answer.

In every weighted n-vertices graphs:

  1. with no negative weighted edges,

  2. with n>10,

  3. in which every weighted edge appears constant number of times(e.g. 1,2,3.., but not n number of times), but graphs, in which every edge has the same value, does not satisfy this condition,

there exists between every two vertices at most 4*n^3.

I tried to draw some graphs and I conclude that all of them satisfy my conditions. But I do not have general explanation.

So is that true? If not, can you say me some counter example?



Hint: consider cases where every weight is very large.

  • $\begingroup$ It came to low quality posts queue and it looks like a comment. What do you think? $\endgroup$ – Evil May 17 '19 at 17:50
  • 1
    $\begingroup$ @Evil I didn't want to post a complete answer because this looks like a homework question. If people don't like it, I'll delete it (or they can delete it for me, via the low quality queue). $\endgroup$ – David Richerby May 17 '19 at 18:58

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