MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.