How to formally prove that if triangle inequality is satisfied in a bunch of edges, then each edge has a positive value?
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&lt;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&lt;0$. Hence, $\alpha\geq 0$.  

It is straightforward to prove that the same reasoning applies in case $\beta&lt;0$ or, equivalently, that $\gamma&lt;0$. Note, however, that from the order we assumed over these costs, $\beta&lt;0$ implies that there are two edge costs which are negative, and that $\gamma&lt;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&lt;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&lt;0$ or $\alpha,\gamma&lt;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&lt;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&lt;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,