3
$\begingroup$

The exact questions states the following:

Suppose that a complete undirected graph $G = (V,E)$ with at least 3 vertices has cost function $c$ that satisfies the triangle inequality. Prove that $c(u,v) \geq 0$ for all $u,v \in V$.

I can intuitively see that $c(u,v)$ is always positive but I don't understand how to present it in a formal proof. From how I see this, for triangle inequality to hold true, $a+b\geq c$, $b+c\geq a$ and $a+c\geq b$. From the above, we can obtain that $a+b\geq a-b$, $b+c\geq b-c$, etc. Since, sum is larger than the difference, it seems to be intuitive that all numbers positive.

I found out how to prove that each edge has positive weight. Now the issue is that there could be an edge that is not part of a triangle. Then how to prove that it is also positive? I guess we have to assume the graph to be complete. Otherwise I don't have any idea on how to solve it.

$\endgroup$
  • $\begingroup$ You don't have to assume that the graph is complete: that's given in the question statement. (Of course the conclusion won't necessarily hold if the graph isn't complete.) $\endgroup$ – Rick Decker Jul 21 '16 at 0:01
  • 2
    $\begingroup$ If you know that $c(u,v) = c(v,u)$ and $c(u,u) = 0$ then $c(u,u) \leq c(u,v) + c(v,u)$ implies $c(u,v) \geq 0$. $\endgroup$ – Yuval Filmus Jul 21 '16 at 8:09
  • $\begingroup$ I don't understand what you're asking. Your problem statement guarantees that $G$ is a complete graph and has at least 3 vertices. Therefore, it's impossible to have an edge that is not part of a triangle. So, the issue can't arise. $\endgroup$ – D.W. Jul 22 '16 at 1:59
  • $\begingroup$ @D.W. Yes, that was the initial question. I solved it while the question was put up on the site. That is the reason the details of the question have been modified. Now after the modification, one interesting problem that arises is that what if "complete" graph is not part of the problem specification. The current accepted answer addresses that issue. I will edit the question to make it clearer as per the accepted answer. $\endgroup$ – aste123 Jul 22 '16 at 2:16
  • $\begingroup$ OK. Editing the question to state that more clearly would be great. (As it currently stands, it sounds like the question is asking about a complete graph, rather than asking about an incomplete graph.) Thanks! $\endgroup$ – D.W. Jul 22 '16 at 2:20
4
$\begingroup$

Let us first go into the proof. Let us then review any further considerations as you do (ie., whether the graph should be complete or not).

Lemma Given an undirected graph $G=(V,E), |V|\geq 3$, and a cost function $c$ defined over $E$, if the triangle inequality is satisfied, then $c(u,v)\geq 0, \forall \langle u,v\rangle \in E$.

Note that the lemma does not require the graph to be complete ---a graph is complete if there is an edge for every pair of vertices, i.e., $\langle u, v\rangle\in E, \forall u, v\in V$.

To prove the statement above take any three vertices $u, v, w\in V$ which are related to each other, i.e., that form a triangle. Let $\alpha=c(u,v), \beta=c(v,w), \gamma=c(u,w)$. Let us assume further without loss of generality that these edge costs are sorted in increasing order of cost: $\alpha\leq\beta\leq\gamma$ ---and this order necessarily exists as discrete optimization problems are usually defined over total orders.

Now, let us proof by contradiction the lemma. There are three different cases (all somehow related to each other, if you manage to understand the first, the others are rather equivalent but I wrote them down here for your convenience).

Case 1 (only one negative edge cost)

Assume that $\alpha<0$. Because triangle inequality is assumed by hypothesis then: $\alpha+\beta\geq\gamma$. To make signs apparent, take absolute values: $|\beta|-|\alpha|\geq |\gamma|$, where I considered $\beta, \gamma\geq 0$. Obviously, $|\gamma|\geq |\gamma| - |\alpha|$ and this is true for all plausible values of $\gamma$ (also negative ones). Thus:

$ |\beta|-|\alpha|\geq |\gamma|\geq |\gamma| - |\alpha| $

leading to $\beta\geq\gamma$ which contradicts our first assumption ($\beta\leq\gamma$).

However, devil's in the details so let us consider the frontier case where $\beta=\gamma$. In this case, take now the other relationship that results from triangle inequality: $\alpha+\gamma\geq\beta$. Since $\beta=\gamma$, the preceding relationship simplifies to $\alpha\geq 0$ which, again, contradicts our second assumption, $\alpha<0$. Hence, $\alpha\geq 0$.

It is straightforward to prove that the same reasoning applies in case $\beta<0$ or, equivalently, that $\gamma<0$. Note, however, that from the order we assumed over these costs, $\beta<0$ implies that there are two edge costs which are negative, and that $\gamma<0$ implies that all of them are negative. These cases are examined next.

Case 2 (two negative edge costs)

Still, there is a caveat in the preceding reasoning. When taking absolute values to make the signs apparent, I considered $\beta, \gamma\geq 0$. You might think that the lemma might not hold in case that two edge costs are negative. Let us assume that both $\alpha, \beta<0$, then as triangle inequality is assumed $\alpha+\beta\geq\gamma$ and again, after taking absolute values the following results: $-|\alpha|-|\beta|\geq|\gamma|$, which is clearly impossible, as the left hand is a negative number and the right hand is a positive number.

And this completes the proof for the second case. If you are thinking of trying the same proof for $\beta, \gamma<0$ or $\alpha,\gamma<0$, note that all edge costs would be necessarily negative as they are sorted in increasing order of cost. This observation leads us to the third case.

Case 3 (all edge costs are negative)

To conclude, what if all edge costs are negative, $\alpha, \beta, \gamma<0$? Oh, well, then it just suffices to combine two expressions resulting from triangle inequality: $\alpha+\beta\geq\gamma$ and, since all of these are negative numbers, then $-|\alpha|-|\beta|\geq -|\gamma|$, but also $\alpha+\gamma\geq\beta$ and, again, because these are all negative numbers then $-|\alpha|-|\gamma|\geq-|\beta|$. Now, the observation is that the first inequality shall hold for values larger or equal than $-|\beta|$ and hence: $-|\alpha|-(-|\alpha|-|\gamma|)\geq -|\gamma|$ which leads to $|\gamma|\geq -|\gamma|$, which is only possible if $\gamma=0$ but this contradicts our assumption that $\gamma<0$ and hence the third case is proven as well by contradiction.

Note to the third case - in case you have difficulty to follow how the last inequality is hold, transform all $\geq$ to $\leq$ by multiplying all inequalities by $-1$. Now, only with positive numbers it might be easier to follow the reasoning.

Observations

Nowhere in the preceding proof I assumed the graph to be complete and, indeed, there might well be a pair of vertices $u,v\in V$ which are not directly related to each other through an edge. What we actually did is to prove that every three vertices connected to each other shall be non-negative given that triangle inequality is verified. This does not prevent some edge costs to be negative. It just suffices that the vertex connected to an edge with a negative cost is not connected to any other vertex. This is true because if the degree of a vertex equals 1 then triangle inequality can not be verified.

Equivalently, if the degree of each vertex is larger or equal than two, triangle inequality can be always verified and, in case it holds, then all edge costs are necessarily non-negative.

Hope this helps,

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for this answer. It helps greatly. Can you tell me if there is any flaw in my method which takes into account that the given graph is complete and hence, all vertices are part of a triangle. $\endgroup$ – aste123 Jul 21 '16 at 18:58
  • 1
    $\begingroup$ Happy to hear that aste! As for your question, there is no flaw: a complete graph is guaranteed to have as many triangle as there might exist and hence you are right. What I tried to prove is that completeness is not a necessary condition and I hoped you'd like the conclusion that it just suffices (i.e., the necessary condition) is for all vertices to have degree 2, as opposed to $|V|-1$ which is the case if the graph is complete. $\endgroup$ – Carlos Linares López Jul 21 '16 at 19:15
  • $\begingroup$ Thanks a lot aste for doing so!! On one hand, it is important closing questions. On the other hand, you boosted my score to 2,000+ :) Very much appreciated! Really. Anyway, I really liked your question. May I know the source? Where did you get this question from? $\endgroup$ – Carlos Linares López Jul 21 '16 at 19:55
  • $\begingroup$ This proof is absurdly overcomplicated. The fact that any edges that form a triangle must be positive follows directly from the definition of the triangle inequality; you don't need separate cases depending on how many are negative. $\endgroup$ – BlueRaja - Danny Pflughoeft Jan 25 '19 at 18:34
  • $\begingroup$ Yeap, you are definitely right ... it certainly follows. I do not believe though it immediately follows but it certainly follows ... $\endgroup$ – Carlos Linares López Jan 26 '19 at 19:18
1
$\begingroup$

There is a much simpler proof.

Say $\{a,b,c\}$ are the weights of edges forming a triangle, with $a<0$ and $b \leq c$. Then $a+b<b \leq c$, so triangle inequality does not hold. Your question is the contrapositive of this.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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