11
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 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
    Commented May 19, 2020 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
    Commented May 19, 2020 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
    Commented May 19, 2020 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
    Commented May 20, 2020 at 11:52
  • 4
    $\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
    Commented May 20, 2020 at 17:27

1 Answer 1

Reset to default
2
$\begingroup$

I think Timothy Chow's comment is right that there is no result about planar graphs with your lemma as an explicit corollary.

I believe the following 2007 research paper by Guido Helden might be of use to you: http://publications.rwth-aachen.de/record/62349/ It is about hamiltonicity of maximal planar graphs and planar triangulations, and starts with a very good exposition.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks a lot for this link! I am very interested in it and will definitely take a look $\endgroup$
    – Claus
    Commented Jul 19, 2020 at 13:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .