0
$\begingroup$

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?

Thanks.

$\endgroup$

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.

1
$\begingroup$

Hint: consider cases where every weight is very large.

$\endgroup$
  • $\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.