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.