This question already has an answer here:

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?



marked as duplicate by Evil, xskxzr, Yuval Filmus, Juho, Discrete lizard May 23 at 15:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


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 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 at 18:58

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