Why can the complete graph K5 be embedded on a torus?
$begingroup$
In the Question Which complete graphs can be embedded on a torus? the poster says, that the complete graph $K_5$ can be embedded on a torus.
But the Euler characteristic of the torus is 0 and the Euler characteristic of $K_5$ is 2. Shouldn't they be the same if $K_5$ can be embedded on the torus?
general-topology graph-theory planar-graph
edited Dec 6 '18 at 13:39
gt6989b
33.9k22455
asked Dec 6 '18 at 13:16
ipponippon
1345
$endgroup$
|
show 1 more comment
$begingroup$
In the Question Which complete graphs can be embedded on a torus? the poster says, that the complete graph $K_5$ can be embedded on a torus.
But the Euler characteristic of the torus is 0 and the Euler characteristic of $K_5$ is 2. Shouldn't they be the same if $K_5$ can be embedded on the torus?
general-topology graph-theory planar-graph
edited Dec 6 '18 at 13:39
gt6989b
33.9k22455
asked Dec 6 '18 at 13:16
ipponippon
1345
$endgroup$
$begingroup$
Have you read the comments on the linked question? This is explained in detail there.
$endgroup$
– saulspatz
Dec 6 '18 at 13:20
$begingroup$
But $K_4$ is planar, so clearly embeds in torus. Do you mean $K_5$ ?
$endgroup$
– coffeemath
Dec 6 '18 at 13:23
1
$begingroup$
@coffeemath sorry i met K5
$endgroup$
– ippon
Dec 6 '18 at 13:27
5
$begingroup$
You can draw $K_5$ in the plane using only one crossing. But then that crossing can go through the torus' hole.
$endgroup$
– coffeemath
Dec 6 '18 at 13:29
1
$begingroup$
bing.com/images/…
$endgroup$
– nafhgood
Dec 6 '18 at 17:24
|
show 1 more comment
$begingroup$
In the Question Which complete graphs can be embedded on a torus? the poster says, that the complete graph $K_5$ can be embedded on a torus.
But the Euler characteristic of the torus is 0 and the Euler characteristic of $K_5$ is 2. Shouldn't they be the same if $K_5$ can be embedded on the torus?
general-topology graph-theory planar-graph
edited Dec 6 '18 at 13:39
gt6989b
33.9k22455
asked Dec 6 '18 at 13:16
ipponippon
1345
$endgroup$
In the Question Which complete graphs can be embedded on a torus? the poster says, that the complete graph $K_5$ can be embedded on a torus.
But the Euler characteristic of the torus is 0 and the Euler characteristic of $K_5$ is 2. Shouldn't they be the same if $K_5$ can be embedded on the torus?
general-topology graph-theory planar-graph
general-topology graph-theory planar-graph
edited Dec 6 '18 at 13:39
gt6989b
33.9k22455
asked Dec 6 '18 at 13:16
ipponippon
1345
edited Dec 6 '18 at 13:39
gt6989b
33.9k22455
asked Dec 6 '18 at 13:16
ipponippon
1345
edited Dec 6 '18 at 13:39
gt6989b
33.9k22455
edited Dec 6 '18 at 13:39
gt6989b
33.9k22455
edited Dec 6 '18 at 13:39
gt6989b
33.9k22455
33.9k22455
asked Dec 6 '18 at 13:16
ipponippon
1345
asked Dec 6 '18 at 13:16
ipponippon
1345
asked Dec 6 '18 at 13:16
ipponippon
1345
1345
$begingroup$
Have you read the comments on the linked question? This is explained in detail there.
$endgroup$
– saulspatz
Dec 6 '18 at 13:20
$begingroup$
But $K_4$ is planar, so clearly embeds in torus. Do you mean $K_5$ ?
$endgroup$
– coffeemath
Dec 6 '18 at 13:23
1
$begingroup$
@coffeemath sorry i met K5
$endgroup$
– ippon
Dec 6 '18 at 13:27
5
$begingroup$
You can draw $K_5$ in the plane using only one crossing. But then that crossing can go through the torus' hole.
$endgroup$
– coffeemath
Dec 6 '18 at 13:29
1
$begingroup$
bing.com/images/…
$endgroup$
– nafhgood
Dec 6 '18 at 17:24
|
show 1 more comment
$begingroup$
Have you read the comments on the linked question? This is explained in detail there.
$endgroup$
– saulspatz
Dec 6 '18 at 13:20
$begingroup$
But $K_4$ is planar, so clearly embeds in torus. Do you mean $K_5$ ?
$endgroup$
– coffeemath
Dec 6 '18 at 13:23
1
$begingroup$
@coffeemath sorry i met K5
$endgroup$
– ippon
Dec 6 '18 at 13:27
5
$begingroup$
You can draw $K_5$ in the plane using only one crossing. But then that crossing can go through the torus' hole.
$endgroup$
– coffeemath
Dec 6 '18 at 13:29
1
$begingroup$
bing.com/images/…
$endgroup$
– nafhgood
Dec 6 '18 at 17:24
$begingroup$
Have you read the comments on the linked question? This is explained in detail there.
$endgroup$
– saulspatz
Dec 6 '18 at 13:20
$begingroup$
Have you read the comments on the linked question? This is explained in detail there.
$endgroup$
– saulspatz
Dec 6 '18 at 13:20
$begingroup$
But $K_4$ is planar, so clearly embeds in torus. Do you mean $K_5$ ?
$endgroup$
– coffeemath
Dec 6 '18 at 13:23
$begingroup$
But $K_4$ is planar, so clearly embeds in torus. Do you mean $K_5$ ?
$endgroup$
– coffeemath
Dec 6 '18 at 13:23
1
1
$begingroup$
@coffeemath sorry i met K5
$endgroup$
– ippon
Dec 6 '18 at 13:27
$begingroup$
@coffeemath sorry i met K5
$endgroup$
– ippon
Dec 6 '18 at 13:27
5
5
$begingroup$
You can draw $K_5$ in the plane using only one crossing. But then that crossing can go through the torus' hole.
$endgroup$
– coffeemath
Dec 6 '18 at 13:29
$begingroup$
You can draw $K_5$ in the plane using only one crossing. But then that crossing can go through the torus' hole.
$endgroup$
– coffeemath
Dec 6 '18 at 13:29
1
1
$begingroup$
bing.com/images/…
$endgroup$
– nafhgood
Dec 6 '18 at 17:24
$begingroup$
bing.com/images/…
$endgroup$
– nafhgood
Dec 6 '18 at 17:24
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
The Euler characteristic of $K_5$ is not $2$. A graph does not have an Euler characteristic.
A graph can have genus, which is the minimum genus of any orientable surface it can be embedded in; since $K_5$ can be embedded in a torus, which has genus $1$, we know that $K_5$ has genus at most $1$. (Since $K_5$ is not planar, we know it does not have genus $0$, therefore it has genus exactly $1$.)
For orientable surfaces, the genus $g$ and the Euler characteristic $chi$ are related by $chi = 2-2g$, so if you wanted to, you could define the Euler characteristic of a graph by this formula. This is not commonly done. By this definition, the Euler characteristic of $K_5$ would be $0$ - the same as that of the torus.
An equivalent way to phrase this definition would be that the Euler characteristic of a graph is the maximum Euler characteristic of any orientable surface it can be embedded into. So we'd conclude that whenever a graph is embedded in an orientable surface, its Euler characteristic must be less than or equal to that of the surface, and that's true here, so we're fine.
answered Dec 6 '18 at 19:21
Misha LavrovMisha Lavrov
45.9k656107
$endgroup$
$begingroup$
I seem to recall seeing a very nice picture in a book (in some bygone millennium) of a map on a torus with $7$ regions, each colored with a different color, and each bordering all the others.
$endgroup$
– bof
Dec 7 '18 at 0:10
$begingroup$
@bof I think even more impressive than that is the Szilassi polyhedron: topologically a torus, it has seven hexagonal sides, and any two sides have an edge in common. (So its dual graph gives an embedding of $K_7$ in the torus.)
$endgroup$
– Misha Lavrov
Dec 7 '18 at 0:15
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%2f3028475%2fwhy-can-the-complete-graph-k5-be-embedded-on-a-torus%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The Euler characteristic of $K_5$ is not $2$. A graph does not have an Euler characteristic.
A graph can have genus, which is the minimum genus of any orientable surface it can be embedded in; since $K_5$ can be embedded in a torus, which has genus $1$, we know that $K_5$ has genus at most $1$. (Since $K_5$ is not planar, we know it does not have genus $0$, therefore it has genus exactly $1$.)
For orientable surfaces, the genus $g$ and the Euler characteristic $chi$ are related by $chi = 2-2g$, so if you wanted to, you could define the Euler characteristic of a graph by this formula. This is not commonly done. By this definition, the Euler characteristic of $K_5$ would be $0$ - the same as that of the torus.
An equivalent way to phrase this definition would be that the Euler characteristic of a graph is the maximum Euler characteristic of any orientable surface it can be embedded into. So we'd conclude that whenever a graph is embedded in an orientable surface, its Euler characteristic must be less than or equal to that of the surface, and that's true here, so we're fine.
answered Dec 6 '18 at 19:21
Misha LavrovMisha Lavrov
45.9k656107
$endgroup$
$begingroup$
I seem to recall seeing a very nice picture in a book (in some bygone millennium) of a map on a torus with $7$ regions, each colored with a different color, and each bordering all the others.
$endgroup$
– bof
Dec 7 '18 at 0:10
$begingroup$
@bof I think even more impressive than that is the Szilassi polyhedron: topologically a torus, it has seven hexagonal sides, and any two sides have an edge in common. (So its dual graph gives an embedding of $K_7$ in the torus.)
$endgroup$
– Misha Lavrov
Dec 7 '18 at 0:15
add a comment |
$begingroup$
The Euler characteristic of $K_5$ is not $2$. A graph does not have an Euler characteristic.
A graph can have genus, which is the minimum genus of any orientable surface it can be embedded in; since $K_5$ can be embedded in a torus, which has genus $1$, we know that $K_5$ has genus at most $1$. (Since $K_5$ is not planar, we know it does not have genus $0$, therefore it has genus exactly $1$.)
For orientable surfaces, the genus $g$ and the Euler characteristic $chi$ are related by $chi = 2-2g$, so if you wanted to, you could define the Euler characteristic of a graph by this formula. This is not commonly done. By this definition, the Euler characteristic of $K_5$ would be $0$ - the same as that of the torus.
An equivalent way to phrase this definition would be that the Euler characteristic of a graph is the maximum Euler characteristic of any orientable surface it can be embedded into. So we'd conclude that whenever a graph is embedded in an orientable surface, its Euler characteristic must be less than or equal to that of the surface, and that's true here, so we're fine.
answered Dec 6 '18 at 19:21
Misha LavrovMisha Lavrov
45.9k656107
$endgroup$
$begingroup$
I seem to recall seeing a very nice picture in a book (in some bygone millennium) of a map on a torus with $7$ regions, each colored with a different color, and each bordering all the others.
$endgroup$
– bof
Dec 7 '18 at 0:10
$begingroup$
@bof I think even more impressive than that is the Szilassi polyhedron: topologically a torus, it has seven hexagonal sides, and any two sides have an edge in common. (So its dual graph gives an embedding of $K_7$ in the torus.)
$endgroup$
– Misha Lavrov
Dec 7 '18 at 0:15
add a comment |
$begingroup$
The Euler characteristic of $K_5$ is not $2$. A graph does not have an Euler characteristic.
A graph can have genus, which is the minimum genus of any orientable surface it can be embedded in; since $K_5$ can be embedded in a torus, which has genus $1$, we know that $K_5$ has genus at most $1$. (Since $K_5$ is not planar, we know it does not have genus $0$, therefore it has genus exactly $1$.)
For orientable surfaces, the genus $g$ and the Euler characteristic $chi$ are related by $chi = 2-2g$, so if you wanted to, you could define the Euler characteristic of a graph by this formula. This is not commonly done. By this definition, the Euler characteristic of $K_5$ would be $0$ - the same as that of the torus.
An equivalent way to phrase this definition would be that the Euler characteristic of a graph is the maximum Euler characteristic of any orientable surface it can be embedded into. So we'd conclude that whenever a graph is embedded in an orientable surface, its Euler characteristic must be less than or equal to that of the surface, and that's true here, so we're fine.
answered Dec 6 '18 at 19:21
Misha LavrovMisha Lavrov
45.9k656107
$endgroup$
The Euler characteristic of $K_5$ is not $2$. A graph does not have an Euler characteristic.
A graph can have genus, which is the minimum genus of any orientable surface it can be embedded in; since $K_5$ can be embedded in a torus, which has genus $1$, we know that $K_5$ has genus at most $1$. (Since $K_5$ is not planar, we know it does not have genus $0$, therefore it has genus exactly $1$.)
For orientable surfaces, the genus $g$ and the Euler characteristic $chi$ are related by $chi = 2-2g$, so if you wanted to, you could define the Euler characteristic of a graph by this formula. This is not commonly done. By this definition, the Euler characteristic of $K_5$ would be $0$ - the same as that of the torus.
An equivalent way to phrase this definition would be that the Euler characteristic of a graph is the maximum Euler characteristic of any orientable surface it can be embedded into. So we'd conclude that whenever a graph is embedded in an orientable surface, its Euler characteristic must be less than or equal to that of the surface, and that's true here, so we're fine.
answered Dec 6 '18 at 19:21
Misha LavrovMisha Lavrov
45.9k656107
answered Dec 6 '18 at 19:21
Misha LavrovMisha Lavrov
45.9k656107
answered Dec 6 '18 at 19:21
Misha LavrovMisha Lavrov
45.9k656107
answered Dec 6 '18 at 19:21
Misha LavrovMisha Lavrov
45.9k656107
45.9k656107
$begingroup$
I seem to recall seeing a very nice picture in a book (in some bygone millennium) of a map on a torus with $7$ regions, each colored with a different color, and each bordering all the others.
$endgroup$
– bof
Dec 7 '18 at 0:10
$begingroup$
@bof I think even more impressive than that is the Szilassi polyhedron: topologically a torus, it has seven hexagonal sides, and any two sides have an edge in common. (So its dual graph gives an embedding of $K_7$ in the torus.)
$endgroup$
– Misha Lavrov
Dec 7 '18 at 0:15
add a comment |
$begingroup$
I seem to recall seeing a very nice picture in a book (in some bygone millennium) of a map on a torus with $7$ regions, each colored with a different color, and each bordering all the others.
$endgroup$
– bof
Dec 7 '18 at 0:10
$begingroup$
@bof I think even more impressive than that is the Szilassi polyhedron: topologically a torus, it has seven hexagonal sides, and any two sides have an edge in common. (So its dual graph gives an embedding of $K_7$ in the torus.)
$endgroup$
– Misha Lavrov
Dec 7 '18 at 0:15
$begingroup$
I seem to recall seeing a very nice picture in a book (in some bygone millennium) of a map on a torus with $7$ regions, each colored with a different color, and each bordering all the others.
$endgroup$
– bof
Dec 7 '18 at 0:10
$begingroup$
I seem to recall seeing a very nice picture in a book (in some bygone millennium) of a map on a torus with $7$ regions, each colored with a different color, and each bordering all the others.
$endgroup$
– bof
Dec 7 '18 at 0:10
$begingroup$
@bof I think even more impressive than that is the Szilassi polyhedron: topologically a torus, it has seven hexagonal sides, and any two sides have an edge in common. (So its dual graph gives an embedding of $K_7$ in the torus.)
$endgroup$
– Misha Lavrov
Dec 7 '18 at 0:15
$begingroup$
@bof I think even more impressive than that is the Szilassi polyhedron: topologically a torus, it has seven hexagonal sides, and any two sides have an edge in common. (So its dual graph gives an embedding of $K_7$ in the torus.)
$endgroup$
– Misha Lavrov
Dec 7 '18 at 0:15
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%2f3028475%2fwhy-can-the-complete-graph-k5-be-embedded-on-a-torus%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
$begingroup$
Have you read the comments on the linked question? This is explained in detail there.
$endgroup$
– saulspatz
Dec 6 '18 at 13:20
$begingroup$
But $K_4$ is planar, so clearly embeds in torus. Do you mean $K_5$ ?
$endgroup$
– coffeemath
Dec 6 '18 at 13:23
1
$begingroup$
@coffeemath sorry i met K5
$endgroup$
– ippon
Dec 6 '18 at 13:27
5
$begingroup$
You can draw $K_5$ in the plane using only one crossing. But then that crossing can go through the torus' hole.
$endgroup$
– coffeemath
Dec 6 '18 at 13:29
1
$begingroup$
bing.com/images/…
$endgroup$
– nafhgood
Dec 6 '18 at 17:24