A discrete form of Jordan curve theorem

Abstract

The paper includes purely co􀀋binatorial proof of a theorem that implies the following theorem, stated by Hugo Steinhaus in [6, p.35]: consider a chessboard (rectang:ular, not necessarily square) with some "mined" squares on. Assume that the king, while moving in a.ccordance with the chess rules, cannot go across the chessboard from the left edge to the right one without meeting a mińed square. Then the rook can go· across' the chessboard from the upper edge to the lower one moving exclusively ·on mined squares. All proofs of the Steinhaus theorem already published (see [5] and remarks on sorhe proofs in [7, p.211]) are incómplete, except the hexagonal variant proved by Gale in [1]. Steinhaus theorem was thought in [6, p.269] as the lemma in the proof of the Brouwer nxed point theorem for the square ( cf. Saskin [5] and Gale [1]). lt can alsó be used as the lemma for the mountain climbing theorem of Homma [2] (see Mioduszewski [3]). In this paper the Steinhaus theorem is used in the proof of a discrete analogue of the Jordan curve theorem (see Stout [8], where different proof is stated; cf. also Rosenfeld [4]).