enter image description here

Is the following lemma a well known result in graph theory?

I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph theory. I have consulted Reinhard Diestel's "Graph Theory" (5th edition, 2017), but could not find it there. So I wanted to ask this question on MO:

Definition: Given an $n\times n$ grid with $n^2$ unit squares. If you randomly place exactly 1 diagonal in each unit square, these diagonals (together with the vertices of the grid) form a graph $G$.

Existence Lemma: $G$ always contains a path of length $\geq n$.

Above you can see a small example on a $6\times 6$ grid. There is a great graphical example for large $n$ by Joseph O’Rourke https://mathoverflow.net/a/112090/156936

I would be grateful if you could let me know whether this is a well known result, specifically in graph theory.

Is there maybe some more general result from graph theory that implies this particular case? I would be very interested in that.

  • 2
    $\begingroup$ In the previous thread, they show there is a path from one side to the other (that was exactly the question). Doesn't that imply your result? $\endgroup$ – verret May 19 at 21:16
  • 2
    $\begingroup$ Well there's a few proofs in that thread so surely, by definition, that means it's a known result? $\endgroup$ – verret May 19 at 21:24
  • 1
    $\begingroup$ Is your question if there is some more general result from graph theory that implies this particular case? $\endgroup$ – Sam Hopkins May 19 at 22:00
  • 1
    $\begingroup$ Related connections to First- and Last-Passage Percolation at this MO question: Shortest grid-graph paths with random diagonal shortcuts. $\endgroup$ – Joseph O'Rourke May 20 at 11:52
  • 3
    $\begingroup$ My guess is that the closest "quotable result" to this is the so-called "Hex theorem" that Hex cannot end in a draw. I think this is due to Gale but you can also read about it here. The Hex theorem does not immediately imply this result but it uses the same ideas. It does seem that there ought to be a more general theorem about planar graphs that includes this theorem and the Hex theorem as special cases, but I am not aware that anyone has stated such a result explicitly. $\endgroup$ – Timothy Chow May 20 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.