Forming a spanning tree; or equivalently, having a unique path between any two cells. Sometimes a few additional connections (adding cycles to the spanning tree) are considered ok.
Really, multiply connected mazes are more interesting and more aesthetically pleasing.
A question, though. If, in 2D, having all walls in one piece is simply connected, and having some islands is multiply connected, what are the possible types of 3D maze (let's call it a cave). You can obviously have simply connected walls, or multiply connected walls (floating shells of rock) but what name would you give the type that has some looping paths but no floating rocks? Do we talk about genus?
