Problem of rooms
$begingroup$
A rectangle is divided into some smaller rectangles.Each two adjacent rectangles share a door which connects them.Prove that we can start from one of the small rectangles and pass them all without crossing a rectangle more than once.
discrete-mathematics graph-theory recreational-mathematics problem-solving
asked Jan 1 at 21:04
Ali FaryadrasAli Faryadras
241
$endgroup$
add a comment |
$begingroup$
A rectangle is divided into some smaller rectangles.Each two adjacent rectangles share a door which connects them.Prove that we can start from one of the small rectangles and pass them all without crossing a rectangle more than once.
discrete-mathematics graph-theory recreational-mathematics problem-solving
asked Jan 1 at 21:04
Ali FaryadrasAli Faryadras
241
$endgroup$
2
$begingroup$
What have you tried so far?
$endgroup$
– user3482749
Jan 1 at 21:05
$begingroup$
@user3482749 I tried to solve this problem by Induction.
$endgroup$
– Ali Faryadras
Jan 1 at 21:09
4
$begingroup$
And? What progress did you make?
$endgroup$
– user3482749
Jan 1 at 21:29
$begingroup$
Not an answer, but there are planar graphs which have no Hamiltonian paths, so the result, if true, must rely on the constraint on the graph implied by the conditions that each room is a rectangle, as is the whole building, and that any two abutting rooms must share a door.
$endgroup$
– Rosie F
Feb 24 at 16:53
add a comment |
$begingroup$
A rectangle is divided into some smaller rectangles.Each two adjacent rectangles share a door which connects them.Prove that we can start from one of the small rectangles and pass them all without crossing a rectangle more than once.
discrete-mathematics graph-theory recreational-mathematics problem-solving
asked Jan 1 at 21:04
Ali FaryadrasAli Faryadras
241
$endgroup$
A rectangle is divided into some smaller rectangles.Each two adjacent rectangles share a door which connects them.Prove that we can start from one of the small rectangles and pass them all without crossing a rectangle more than once.
discrete-mathematics graph-theory recreational-mathematics problem-solving
discrete-mathematics graph-theory recreational-mathematics problem-solving
asked Jan 1 at 21:04
Ali FaryadrasAli Faryadras
241
asked Jan 1 at 21:04
Ali FaryadrasAli Faryadras
241
asked Jan 1 at 21:04
Ali FaryadrasAli Faryadras
241
asked Jan 1 at 21:04
Ali FaryadrasAli Faryadras
241
asked Jan 1 at 21:04
Ali FaryadrasAli Faryadras
241
241
2
$begingroup$
What have you tried so far?
$endgroup$
– user3482749
Jan 1 at 21:05
$begingroup$
@user3482749 I tried to solve this problem by Induction.
$endgroup$
– Ali Faryadras
Jan 1 at 21:09
4
$begingroup$
And? What progress did you make?
$endgroup$
– user3482749
Jan 1 at 21:29
$begingroup$
Not an answer, but there are planar graphs which have no Hamiltonian paths, so the result, if true, must rely on the constraint on the graph implied by the conditions that each room is a rectangle, as is the whole building, and that any two abutting rooms must share a door.
$endgroup$
– Rosie F
Feb 24 at 16:53
add a comment |
2
$begingroup$
What have you tried so far?
$endgroup$
– user3482749
Jan 1 at 21:05
$begingroup$
@user3482749 I tried to solve this problem by Induction.
$endgroup$
– Ali Faryadras
Jan 1 at 21:09
4
$begingroup$
And? What progress did you make?
$endgroup$
– user3482749
Jan 1 at 21:29
$begingroup$
Not an answer, but there are planar graphs which have no Hamiltonian paths, so the result, if true, must rely on the constraint on the graph implied by the conditions that each room is a rectangle, as is the whole building, and that any two abutting rooms must share a door.
$endgroup$
– Rosie F
Feb 24 at 16:53
2
2
$begingroup$
What have you tried so far?
$endgroup$
– user3482749
Jan 1 at 21:05
$begingroup$
What have you tried so far?
$endgroup$
– user3482749
Jan 1 at 21:05
$begingroup$
@user3482749 I tried to solve this problem by Induction.
$endgroup$
– Ali Faryadras
Jan 1 at 21:09
$begingroup$
@user3482749 I tried to solve this problem by Induction.
$endgroup$
– Ali Faryadras
Jan 1 at 21:09
4
4
$begingroup$
And? What progress did you make?
$endgroup$
– user3482749
Jan 1 at 21:29
$begingroup$
And? What progress did you make?
$endgroup$
– user3482749
Jan 1 at 21:29
$begingroup$
Not an answer, but there are planar graphs which have no Hamiltonian paths, so the result, if true, must rely on the constraint on the graph implied by the conditions that each room is a rectangle, as is the whole building, and that any two abutting rooms must share a door.
$endgroup$
– Rosie F
Feb 24 at 16:53
$begingroup$
Not an answer, but there are planar graphs which have no Hamiltonian paths, so the result, if true, must rely on the constraint on the graph implied by the conditions that each room is a rectangle, as is the whole building, and that any two abutting rooms must share a door.
$endgroup$
– Rosie F
Feb 24 at 16:53
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Here's a tip in the right direction. The main difficulty of an inductive argument would be the following hypothetical case:
Here, it is not obvious how to adapt the pre-existing path to to include this new rectangle. So, why not make the inductive hypothesis be that there exists a path which never exits a rectangle, $r$, from the same "side" that $r$ was entered from, avoiding this problem altogether. With that inductive hypothesis, here’s the case work:
Hopefully everything is clear now?
answered Jan 2 at 6:06
Zachary HunterZachary Hunter
1,055314
$endgroup$
$begingroup$
Do you have another idea without using induction?
$endgroup$
– Ali Faryadras
Jan 2 at 9:28
$begingroup$
induction is by far most natural to me, are you still having difficulty?
$endgroup$
– Zachary Hunter
Jan 2 at 14:22
$begingroup$
Have you tried anything since?
$endgroup$
– Zachary Hunter
Jan 3 at 3:20
$begingroup$
please try to provide further guidance.
$endgroup$
– Ali Faryadras
Jan 5 at 12:12
1
$begingroup$
Exactly what are the steps you consider? If they all amount to bisecting one of the existing rectangles, then not all tilings of a rectangle with rectangles can be made that way. (Consider filling a 9x9 square with four 2x1 rectangles along the edges and a single 1x1 square in the middle).
$endgroup$
– Henning Makholm
Jan 6 at 14:24
|
show 1 more comment
$begingroup$
Convert the rectangular structure to a graph, where each door becomes a vertex and each room becomes an edge. Since each door connects exactly two rooms, each vertex is therefore of degree two. Since no vertex is of odd degree, a Eulerian cycle is possible, i.e. each room/edge/bridge can be visited without repetition.
answered Jan 6 at 14:10
GarryBGarryB
844
$endgroup$
1
$begingroup$
Since rooms will generally have more than two doors, this requires thinking about "edges" that connect more than two "vertices". That is definitely not a standard concept of graphs, so the standard theorems (like the one you're appealing to) will not work.
$endgroup$
– Henning Makholm
Jan 6 at 14:27
1
$begingroup$
And "a Eulerian cycle is possible" is too strong a conclusion anyway. There are easy room layouts that will only allow for an Eulerian trail (which may end in a different room from the one it started at).
$endgroup$
– Henning Makholm
Jan 6 at 14:28
$begingroup$
Yes, I was thinking of a simple room structure which produced a simple graph.
$endgroup$
– GarryB
Jan 7 at 15:57
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3058878%2fproblem-of-rooms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here's a tip in the right direction. The main difficulty of an inductive argument would be the following hypothetical case:
Here, it is not obvious how to adapt the pre-existing path to to include this new rectangle. So, why not make the inductive hypothesis be that there exists a path which never exits a rectangle, $r$, from the same "side" that $r$ was entered from, avoiding this problem altogether. With that inductive hypothesis, here’s the case work:
Hopefully everything is clear now?
answered Jan 2 at 6:06
Zachary HunterZachary Hunter
1,055314
$endgroup$
$begingroup$
Do you have another idea without using induction?
$endgroup$
– Ali Faryadras
Jan 2 at 9:28
$begingroup$
induction is by far most natural to me, are you still having difficulty?
$endgroup$
– Zachary Hunter
Jan 2 at 14:22
$begingroup$
Have you tried anything since?
$endgroup$
– Zachary Hunter
Jan 3 at 3:20
$begingroup$
please try to provide further guidance.
$endgroup$
– Ali Faryadras
Jan 5 at 12:12
1
$begingroup$
Exactly what are the steps you consider? If they all amount to bisecting one of the existing rectangles, then not all tilings of a rectangle with rectangles can be made that way. (Consider filling a 9x9 square with four 2x1 rectangles along the edges and a single 1x1 square in the middle).
$endgroup$
– Henning Makholm
Jan 6 at 14:24
|
show 1 more comment
$begingroup$
Here's a tip in the right direction. The main difficulty of an inductive argument would be the following hypothetical case:
Here, it is not obvious how to adapt the pre-existing path to to include this new rectangle. So, why not make the inductive hypothesis be that there exists a path which never exits a rectangle, $r$, from the same "side" that $r$ was entered from, avoiding this problem altogether. With that inductive hypothesis, here’s the case work:
Hopefully everything is clear now?
answered Jan 2 at 6:06
Zachary HunterZachary Hunter
1,055314
$endgroup$
$begingroup$
Do you have another idea without using induction?
$endgroup$
– Ali Faryadras
Jan 2 at 9:28
$begingroup$
induction is by far most natural to me, are you still having difficulty?
$endgroup$
– Zachary Hunter
Jan 2 at 14:22
$begingroup$
Have you tried anything since?
$endgroup$
– Zachary Hunter
Jan 3 at 3:20
$begingroup$
please try to provide further guidance.
$endgroup$
– Ali Faryadras
Jan 5 at 12:12
1
$begingroup$
Exactly what are the steps you consider? If they all amount to bisecting one of the existing rectangles, then not all tilings of a rectangle with rectangles can be made that way. (Consider filling a 9x9 square with four 2x1 rectangles along the edges and a single 1x1 square in the middle).
$endgroup$
– Henning Makholm
Jan 6 at 14:24
|
show 1 more comment
$begingroup$
Here's a tip in the right direction. The main difficulty of an inductive argument would be the following hypothetical case:
Here, it is not obvious how to adapt the pre-existing path to to include this new rectangle. So, why not make the inductive hypothesis be that there exists a path which never exits a rectangle, $r$, from the same "side" that $r$ was entered from, avoiding this problem altogether. With that inductive hypothesis, here’s the case work:
Hopefully everything is clear now?
answered Jan 2 at 6:06
Zachary HunterZachary Hunter
1,055314
$endgroup$
Here's a tip in the right direction. The main difficulty of an inductive argument would be the following hypothetical case:
Here, it is not obvious how to adapt the pre-existing path to to include this new rectangle. So, why not make the inductive hypothesis be that there exists a path which never exits a rectangle, $r$, from the same "side" that $r$ was entered from, avoiding this problem altogether. With that inductive hypothesis, here’s the case work:
Hopefully everything is clear now?
answered Jan 2 at 6:06
Zachary HunterZachary Hunter
1,055314
edited Jan 5 at 15:36
answered Jan 2 at 6:06
Zachary HunterZachary Hunter
1,055314
answered Jan 2 at 6:06
Zachary HunterZachary Hunter
1,055314
answered Jan 2 at 6:06
Zachary HunterZachary Hunter
1,055314
1,055314
$begingroup$
Do you have another idea without using induction?
$endgroup$
– Ali Faryadras
Jan 2 at 9:28
$begingroup$
induction is by far most natural to me, are you still having difficulty?
$endgroup$
– Zachary Hunter
Jan 2 at 14:22
$begingroup$
Have you tried anything since?
$endgroup$
– Zachary Hunter
Jan 3 at 3:20
$begingroup$
please try to provide further guidance.
$endgroup$
– Ali Faryadras
Jan 5 at 12:12
1
$begingroup$
Exactly what are the steps you consider? If they all amount to bisecting one of the existing rectangles, then not all tilings of a rectangle with rectangles can be made that way. (Consider filling a 9x9 square with four 2x1 rectangles along the edges and a single 1x1 square in the middle).
$endgroup$
– Henning Makholm
Jan 6 at 14:24
|
show 1 more comment
$begingroup$
Do you have another idea without using induction?
$endgroup$
– Ali Faryadras
Jan 2 at 9:28
$begingroup$
induction is by far most natural to me, are you still having difficulty?
$endgroup$
– Zachary Hunter
Jan 2 at 14:22
$begingroup$
Have you tried anything since?
$endgroup$
– Zachary Hunter
Jan 3 at 3:20
$begingroup$
please try to provide further guidance.
$endgroup$
– Ali Faryadras
Jan 5 at 12:12
1
$begingroup$
Exactly what are the steps you consider? If they all amount to bisecting one of the existing rectangles, then not all tilings of a rectangle with rectangles can be made that way. (Consider filling a 9x9 square with four 2x1 rectangles along the edges and a single 1x1 square in the middle).
$endgroup$
– Henning Makholm
Jan 6 at 14:24
$begingroup$
Do you have another idea without using induction?
$endgroup$
– Ali Faryadras
Jan 2 at 9:28
$begingroup$
Do you have another idea without using induction?
$endgroup$
– Ali Faryadras
Jan 2 at 9:28
$begingroup$
induction is by far most natural to me, are you still having difficulty?
$endgroup$
– Zachary Hunter
Jan 2 at 14:22
$begingroup$
induction is by far most natural to me, are you still having difficulty?
$endgroup$
– Zachary Hunter
Jan 2 at 14:22
$begingroup$
Have you tried anything since?
$endgroup$
– Zachary Hunter
Jan 3 at 3:20
$begingroup$
Have you tried anything since?
$endgroup$
– Zachary Hunter
Jan 3 at 3:20
$begingroup$
please try to provide further guidance.
$endgroup$
– Ali Faryadras
Jan 5 at 12:12
$begingroup$
please try to provide further guidance.
$endgroup$
– Ali Faryadras
Jan 5 at 12:12
1
1
$begingroup$
Exactly what are the steps you consider? If they all amount to bisecting one of the existing rectangles, then not all tilings of a rectangle with rectangles can be made that way. (Consider filling a 9x9 square with four 2x1 rectangles along the edges and a single 1x1 square in the middle).
$endgroup$
– Henning Makholm
Jan 6 at 14:24
$begingroup$
Exactly what are the steps you consider? If they all amount to bisecting one of the existing rectangles, then not all tilings of a rectangle with rectangles can be made that way. (Consider filling a 9x9 square with four 2x1 rectangles along the edges and a single 1x1 square in the middle).
$endgroup$
– Henning Makholm
Jan 6 at 14:24
|
show 1 more comment
$begingroup$
Convert the rectangular structure to a graph, where each door becomes a vertex and each room becomes an edge. Since each door connects exactly two rooms, each vertex is therefore of degree two. Since no vertex is of odd degree, a Eulerian cycle is possible, i.e. each room/edge/bridge can be visited without repetition.
answered Jan 6 at 14:10
GarryBGarryB
844
$endgroup$
1
$begingroup$
Since rooms will generally have more than two doors, this requires thinking about "edges" that connect more than two "vertices". That is definitely not a standard concept of graphs, so the standard theorems (like the one you're appealing to) will not work.
$endgroup$
– Henning Makholm
Jan 6 at 14:27
1
$begingroup$
And "a Eulerian cycle is possible" is too strong a conclusion anyway. There are easy room layouts that will only allow for an Eulerian trail (which may end in a different room from the one it started at).
$endgroup$
– Henning Makholm
Jan 6 at 14:28
$begingroup$
Yes, I was thinking of a simple room structure which produced a simple graph.
$endgroup$
– GarryB
Jan 7 at 15:57
add a comment |
$begingroup$
Convert the rectangular structure to a graph, where each door becomes a vertex and each room becomes an edge. Since each door connects exactly two rooms, each vertex is therefore of degree two. Since no vertex is of odd degree, a Eulerian cycle is possible, i.e. each room/edge/bridge can be visited without repetition.
answered Jan 6 at 14:10
GarryBGarryB
844
$endgroup$
1
$begingroup$
Since rooms will generally have more than two doors, this requires thinking about "edges" that connect more than two "vertices". That is definitely not a standard concept of graphs, so the standard theorems (like the one you're appealing to) will not work.
$endgroup$
– Henning Makholm
Jan 6 at 14:27
1
$begingroup$
And "a Eulerian cycle is possible" is too strong a conclusion anyway. There are easy room layouts that will only allow for an Eulerian trail (which may end in a different room from the one it started at).
$endgroup$
– Henning Makholm
Jan 6 at 14:28
$begingroup$
Yes, I was thinking of a simple room structure which produced a simple graph.
$endgroup$
– GarryB
Jan 7 at 15:57
add a comment |
$begingroup$
Convert the rectangular structure to a graph, where each door becomes a vertex and each room becomes an edge. Since each door connects exactly two rooms, each vertex is therefore of degree two. Since no vertex is of odd degree, a Eulerian cycle is possible, i.e. each room/edge/bridge can be visited without repetition.
answered Jan 6 at 14:10
GarryBGarryB
844
$endgroup$
Convert the rectangular structure to a graph, where each door becomes a vertex and each room becomes an edge. Since each door connects exactly two rooms, each vertex is therefore of degree two. Since no vertex is of odd degree, a Eulerian cycle is possible, i.e. each room/edge/bridge can be visited without repetition.
answered Jan 6 at 14:10
GarryBGarryB
844
answered Jan 6 at 14:10
GarryBGarryB
844
answered Jan 6 at 14:10
GarryBGarryB
844
answered Jan 6 at 14:10
GarryBGarryB
844
844
1
$begingroup$
Since rooms will generally have more than two doors, this requires thinking about "edges" that connect more than two "vertices". That is definitely not a standard concept of graphs, so the standard theorems (like the one you're appealing to) will not work.
$endgroup$
– Henning Makholm
Jan 6 at 14:27
1
$begingroup$
And "a Eulerian cycle is possible" is too strong a conclusion anyway. There are easy room layouts that will only allow for an Eulerian trail (which may end in a different room from the one it started at).
$endgroup$
– Henning Makholm
Jan 6 at 14:28
$begingroup$
Yes, I was thinking of a simple room structure which produced a simple graph.
$endgroup$
– GarryB
Jan 7 at 15:57
add a comment |
1
$begingroup$
Since rooms will generally have more than two doors, this requires thinking about "edges" that connect more than two "vertices". That is definitely not a standard concept of graphs, so the standard theorems (like the one you're appealing to) will not work.
$endgroup$
– Henning Makholm
Jan 6 at 14:27
1
$begingroup$
And "a Eulerian cycle is possible" is too strong a conclusion anyway. There are easy room layouts that will only allow for an Eulerian trail (which may end in a different room from the one it started at).
$endgroup$
– Henning Makholm
Jan 6 at 14:28
$begingroup$
Yes, I was thinking of a simple room structure which produced a simple graph.
$endgroup$
– GarryB
Jan 7 at 15:57
1
1
$begingroup$
Since rooms will generally have more than two doors, this requires thinking about "edges" that connect more than two "vertices". That is definitely not a standard concept of graphs, so the standard theorems (like the one you're appealing to) will not work.
$endgroup$
– Henning Makholm
Jan 6 at 14:27
$begingroup$
Since rooms will generally have more than two doors, this requires thinking about "edges" that connect more than two "vertices". That is definitely not a standard concept of graphs, so the standard theorems (like the one you're appealing to) will not work.
$endgroup$
– Henning Makholm
Jan 6 at 14:27
1
1
$begingroup$
And "a Eulerian cycle is possible" is too strong a conclusion anyway. There are easy room layouts that will only allow for an Eulerian trail (which may end in a different room from the one it started at).
$endgroup$
– Henning Makholm
Jan 6 at 14:28
$begingroup$
And "a Eulerian cycle is possible" is too strong a conclusion anyway. There are easy room layouts that will only allow for an Eulerian trail (which may end in a different room from the one it started at).
$endgroup$
– Henning Makholm
Jan 6 at 14:28
$begingroup$
Yes, I was thinking of a simple room structure which produced a simple graph.
$endgroup$
– GarryB
Jan 7 at 15:57
$begingroup$
Yes, I was thinking of a simple room structure which produced a simple graph.
$endgroup$
– GarryB
Jan 7 at 15:57
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3058878%2fproblem-of-rooms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
What have you tried so far?
$endgroup$
– user3482749
Jan 1 at 21:05
$begingroup$
@user3482749 I tried to solve this problem by Induction.
$endgroup$
– Ali Faryadras
Jan 1 at 21:09
4
$begingroup$
And? What progress did you make?
$endgroup$
– user3482749
Jan 1 at 21:29
$begingroup$
Not an answer, but there are planar graphs which have no Hamiltonian paths, so the result, if true, must rely on the constraint on the graph implied by the conditions that each room is a rectangle, as is the whole building, and that any two abutting rooms must share a door.
$endgroup$
– Rosie F
Feb 24 at 16:53