Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.