0
$\begingroup$

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.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
1
$\begingroup$

Hint: consider cases where every weight is very large.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It came to low quality posts queue and it looks like a comment. What do you think? $\endgroup$
    – Evil
    May 17, 2019 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, 2019 at 18:58

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