# Non-trivial lower bound on the number of “Graph Diagonals”

The definition of Graph Diagonals, that are the subject of this question, is based on the notions of crossing edges and on connected graphs:

Two edges $AC$ and $BD$ of a complete, symmetric and weighted graph are said to be crossing (each other) iff

$A$, $B$, $C$ and, $D$ are distinct vertices and
$AC+BD > AB+CD$ and $AC+BD > AD+BC$

An edge $AB$ of a complete, symmetric and weighted graph,is then defined to be a diagonal of the graph iff

removing from the graph all edges that are crossing edge $AB$ and
removing vertices $A$ and $B$

disconnects the graph

One important property of those graph diagonals is that they can't appear in an optimal tour through all vertices of the graph.

From some experiments I observed that at least every 6th edge was such a diagonal and with increasing number of vertices almost all vertices were adjacent to such a diagonal.

My question is, whether the lower bound of $n(n+1)/12$ diagonals can be confirmed.

-
Can you clarify what you mean by a "symmetric" complete graph? – Casteels Mar 9 '13 at 22:28
"symmetric" means that the edges are undirected (I had the symmetric TSP in mind, but I agree that I should have been more precise here). A complete graph is one where every pair of vertices corresponds to an edge with an associated weight. – Manfred Weis Mar 10 '13 at 6:16
Oh ok, thanks. Next question: Does AC mean the weight of the edge from vertex A to vertex C? If so, then setting all weights to 1 gives zero diagonals... – Casteels Mar 10 '13 at 20:10