Mixing
If $G$ is a bipartite Euler and Hamiltonian graph, prove that complement of $G$, $bar G$ is not Eulers.
$begingroup$
I would like to know if my proof of the statement in the title is correct.
So, I started like this:
As $G$ is a bipartite graph, it has two sets $X$ and $Y$. Using the condition $G$ is Hamiltonian, then $|X| = |Y|$.
As $G$ is also Eulerian, stands $d_G(v)$ is even $forall v in V(G)$, where $V(G)$ is set of vertices of the graph $G$.
Now, let's look at some vertex $v in X(G)$. As stated above, it's degree is even. Let's look at two possible cases:
- If $|X| = |Y|$ is even too, then in $bar G$, $v$ will be connected with all the remaining vertices from $X$. That vertex $v$ will also be connected with remaining vertices from $Y$, with which it wasn't connected in the graph $G$. That is, $d_bar G(v) = |X| - 1 + m$, where $m$ represents number of remaining vertices from $Y$. As $|X|$ is even, then $|X| - 1$ is odd, and $m$ is also even, because $d_G(v)$ is even and $|Y|$ is even, so the remaining number of vertices, $m$ is even too. Sum of an even and an odd number is odd, so $d_bar G(v)$ is odd. That means $bar G$ is not Eulerian;
- If $|X| = |Y|$ is odd, in $bar G$, $v$ will be connected with all the remaining vertices from $X$ and all the remaining vertices from $Y$, and let's call the number of $Y$ remaining vertices $m$. As $|Y|$ is odd and $d_G(v)$ is even, then $m$ is odd. Degree of $v$ in $bar G$ is once again $d_bar G(v) = |X| - 1 + m$, but this time $|X| - 1$ is even, and $m$ is odd. $d_bar G(v)$ is odd and that means $bar G$ is not Eulerian.
Thank You!
Excuse me for my bad English, I tried to write this as clear as I can.
discrete-mathematics graph-theory bipartite-graph
asked Jan 16 at 19:04
HarisHaris
263
$endgroup$
add a comment |
$begingroup$
I would like to know if my proof of the statement in the title is correct.
So, I started like this:
As $G$ is a bipartite graph, it has two sets $X$ and $Y$. Using the condition $G$ is Hamiltonian, then $|X| = |Y|$.
As $G$ is also Eulerian, stands $d_G(v)$ is even $forall v in V(G)$, where $V(G)$ is set of vertices of the graph $G$.
Now, let's look at some vertex $v in X(G)$. As stated above, it's degree is even. Let's look at two possible cases:
- If $|X| = |Y|$ is even too, then in $bar G$, $v$ will be connected with all the remaining vertices from $X$. That vertex $v$ will also be connected with remaining vertices from $Y$, with which it wasn't connected in the graph $G$. That is, $d_bar G(v) = |X| - 1 + m$, where $m$ represents number of remaining vertices from $Y$. As $|X|$ is even, then $|X| - 1$ is odd, and $m$ is also even, because $d_G(v)$ is even and $|Y|$ is even, so the remaining number of vertices, $m$ is even too. Sum of an even and an odd number is odd, so $d_bar G(v)$ is odd. That means $bar G$ is not Eulerian;
- If $|X| = |Y|$ is odd, in $bar G$, $v$ will be connected with all the remaining vertices from $X$ and all the remaining vertices from $Y$, and let's call the number of $Y$ remaining vertices $m$. As $|Y|$ is odd and $d_G(v)$ is even, then $m$ is odd. Degree of $v$ in $bar G$ is once again $d_bar G(v) = |X| - 1 + m$, but this time $|X| - 1$ is even, and $m$ is odd. $d_bar G(v)$ is odd and that means $bar G$ is not Eulerian.
Thank You!
Excuse me for my bad English, I tried to write this as clear as I can.
discrete-mathematics graph-theory bipartite-graph
asked Jan 16 at 19:04
HarisHaris
263
$endgroup$
add a comment |
$begingroup$
I would like to know if my proof of the statement in the title is correct.
So, I started like this:
As $G$ is a bipartite graph, it has two sets $X$ and $Y$. Using the condition $G$ is Hamiltonian, then $|X| = |Y|$.
As $G$ is also Eulerian, stands $d_G(v)$ is even $forall v in V(G)$, where $V(G)$ is set of vertices of the graph $G$.
Now, let's look at some vertex $v in X(G)$. As stated above, it's degree is even. Let's look at two possible cases:
- If $|X| = |Y|$ is even too, then in $bar G$, $v$ will be connected with all the remaining vertices from $X$. That vertex $v$ will also be connected with remaining vertices from $Y$, with which it wasn't connected in the graph $G$. That is, $d_bar G(v) = |X| - 1 + m$, where $m$ represents number of remaining vertices from $Y$. As $|X|$ is even, then $|X| - 1$ is odd, and $m$ is also even, because $d_G(v)$ is even and $|Y|$ is even, so the remaining number of vertices, $m$ is even too. Sum of an even and an odd number is odd, so $d_bar G(v)$ is odd. That means $bar G$ is not Eulerian;
- If $|X| = |Y|$ is odd, in $bar G$, $v$ will be connected with all the remaining vertices from $X$ and all the remaining vertices from $Y$, and let's call the number of $Y$ remaining vertices $m$. As $|Y|$ is odd and $d_G(v)$ is even, then $m$ is odd. Degree of $v$ in $bar G$ is once again $d_bar G(v) = |X| - 1 + m$, but this time $|X| - 1$ is even, and $m$ is odd. $d_bar G(v)$ is odd and that means $bar G$ is not Eulerian.
Thank You!
Excuse me for my bad English, I tried to write this as clear as I can.
discrete-mathematics graph-theory bipartite-graph
asked Jan 16 at 19:04
HarisHaris
263
$endgroup$
I would like to know if my proof of the statement in the title is correct.
So, I started like this:
As $G$ is a bipartite graph, it has two sets $X$ and $Y$. Using the condition $G$ is Hamiltonian, then $|X| = |Y|$.
As $G$ is also Eulerian, stands $d_G(v)$ is even $forall v in V(G)$, where $V(G)$ is set of vertices of the graph $G$.
Now, let's look at some vertex $v in X(G)$. As stated above, it's degree is even. Let's look at two possible cases:
- If $|X| = |Y|$ is even too, then in $bar G$, $v$ will be connected with all the remaining vertices from $X$. That vertex $v$ will also be connected with remaining vertices from $Y$, with which it wasn't connected in the graph $G$. That is, $d_bar G(v) = |X| - 1 + m$, where $m$ represents number of remaining vertices from $Y$. As $|X|$ is even, then $|X| - 1$ is odd, and $m$ is also even, because $d_G(v)$ is even and $|Y|$ is even, so the remaining number of vertices, $m$ is even too. Sum of an even and an odd number is odd, so $d_bar G(v)$ is odd. That means $bar G$ is not Eulerian;
- If $|X| = |Y|$ is odd, in $bar G$, $v$ will be connected with all the remaining vertices from $X$ and all the remaining vertices from $Y$, and let's call the number of $Y$ remaining vertices $m$. As $|Y|$ is odd and $d_G(v)$ is even, then $m$ is odd. Degree of $v$ in $bar G$ is once again $d_bar G(v) = |X| - 1 + m$, but this time $|X| - 1$ is even, and $m$ is odd. $d_bar G(v)$ is odd and that means $bar G$ is not Eulerian.
Thank You!
Excuse me for my bad English, I tried to write this as clear as I can.
discrete-mathematics graph-theory bipartite-graph
discrete-mathematics graph-theory bipartite-graph
asked Jan 16 at 19:04
HarisHaris
263
asked Jan 16 at 19:04
HarisHaris
263
asked Jan 16 at 19:04
HarisHaris
263
asked Jan 16 at 19:04
HarisHaris
263
asked Jan 16 at 19:04
HarisHaris
263
263
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your line of reasoning is correct. There is a simpler way to prove/disprove this though: If $G$ is bipartite Eulerian with both sides having the same number $l$ of vertices, then the number $n_G$ of vertices in $G$ is $2l$ which is even. This implies that every vertex in the complement $bar{G}$ of $G$ will have odd degree [indeed, $d_{bar{G}}(v) = n_G-1-d_G(v) =2l-1-d_G(v)$ where $d_G(v)$ the degree of vertex $v$ in $G$; make sure you see why this is so and why it is odd]. So $bar{G}$ is not Eulerian.
[However, $bar{G}$ can still be Hamiltonian itself. In fact, if $G$ is a cycle on (say) 16 vertices then $bar{G}$ is Hamiltonian.]
answered Jan 16 at 19:10
MikeMike
4,171412
$endgroup$
1
$begingroup$
Oh, yeah, I see. Because the two sides have the same number of vertices, there could only be even number of vertices in G. So, degree of complement of every vertex would be n - 1 - d(v), which is odd. Thank You!
$endgroup$
– Haris
Jan 16 at 19:19
$begingroup$
Glad I could help. And I should have pointed out originally that your line of reasoning is correct.
$endgroup$
– Mike
Jan 16 at 19:26
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%2f3076152%2fif-g-is-a-bipartite-euler-and-hamiltonian-graph-prove-that-complement-of-g%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$
Your line of reasoning is correct. There is a simpler way to prove/disprove this though: If $G$ is bipartite Eulerian with both sides having the same number $l$ of vertices, then the number $n_G$ of vertices in $G$ is $2l$ which is even. This implies that every vertex in the complement $bar{G}$ of $G$ will have odd degree [indeed, $d_{bar{G}}(v) = n_G-1-d_G(v) =2l-1-d_G(v)$ where $d_G(v)$ the degree of vertex $v$ in $G$; make sure you see why this is so and why it is odd]. So $bar{G}$ is not Eulerian.
[However, $bar{G}$ can still be Hamiltonian itself. In fact, if $G$ is a cycle on (say) 16 vertices then $bar{G}$ is Hamiltonian.]
answered Jan 16 at 19:10
MikeMike
4,171412
$endgroup$
1
$begingroup$
Oh, yeah, I see. Because the two sides have the same number of vertices, there could only be even number of vertices in G. So, degree of complement of every vertex would be n - 1 - d(v), which is odd. Thank You!
$endgroup$
– Haris
Jan 16 at 19:19
$begingroup$
Glad I could help. And I should have pointed out originally that your line of reasoning is correct.
$endgroup$
– Mike
Jan 16 at 19:26
add a comment |
$begingroup$
Your line of reasoning is correct. There is a simpler way to prove/disprove this though: If $G$ is bipartite Eulerian with both sides having the same number $l$ of vertices, then the number $n_G$ of vertices in $G$ is $2l$ which is even. This implies that every vertex in the complement $bar{G}$ of $G$ will have odd degree [indeed, $d_{bar{G}}(v) = n_G-1-d_G(v) =2l-1-d_G(v)$ where $d_G(v)$ the degree of vertex $v$ in $G$; make sure you see why this is so and why it is odd]. So $bar{G}$ is not Eulerian.
[However, $bar{G}$ can still be Hamiltonian itself. In fact, if $G$ is a cycle on (say) 16 vertices then $bar{G}$ is Hamiltonian.]
answered Jan 16 at 19:10
MikeMike
4,171412
$endgroup$
1
$begingroup$
Oh, yeah, I see. Because the two sides have the same number of vertices, there could only be even number of vertices in G. So, degree of complement of every vertex would be n - 1 - d(v), which is odd. Thank You!
$endgroup$
– Haris
Jan 16 at 19:19
$begingroup$
Glad I could help. And I should have pointed out originally that your line of reasoning is correct.
$endgroup$
– Mike
Jan 16 at 19:26
add a comment |
$begingroup$
Your line of reasoning is correct. There is a simpler way to prove/disprove this though: If $G$ is bipartite Eulerian with both sides having the same number $l$ of vertices, then the number $n_G$ of vertices in $G$ is $2l$ which is even. This implies that every vertex in the complement $bar{G}$ of $G$ will have odd degree [indeed, $d_{bar{G}}(v) = n_G-1-d_G(v) =2l-1-d_G(v)$ where $d_G(v)$ the degree of vertex $v$ in $G$; make sure you see why this is so and why it is odd]. So $bar{G}$ is not Eulerian.
[However, $bar{G}$ can still be Hamiltonian itself. In fact, if $G$ is a cycle on (say) 16 vertices then $bar{G}$ is Hamiltonian.]
answered Jan 16 at 19:10
MikeMike
4,171412
$endgroup$
Your line of reasoning is correct. There is a simpler way to prove/disprove this though: If $G$ is bipartite Eulerian with both sides having the same number $l$ of vertices, then the number $n_G$ of vertices in $G$ is $2l$ which is even. This implies that every vertex in the complement $bar{G}$ of $G$ will have odd degree [indeed, $d_{bar{G}}(v) = n_G-1-d_G(v) =2l-1-d_G(v)$ where $d_G(v)$ the degree of vertex $v$ in $G$; make sure you see why this is so and why it is odd]. So $bar{G}$ is not Eulerian.
[However, $bar{G}$ can still be Hamiltonian itself. In fact, if $G$ is a cycle on (say) 16 vertices then $bar{G}$ is Hamiltonian.]
answered Jan 16 at 19:10
MikeMike
4,171412
edited Jan 16 at 19:21
answered Jan 16 at 19:10
MikeMike
4,171412
answered Jan 16 at 19:10
MikeMike
4,171412
answered Jan 16 at 19:10
MikeMike
4,171412
4,171412
1
$begingroup$
Oh, yeah, I see. Because the two sides have the same number of vertices, there could only be even number of vertices in G. So, degree of complement of every vertex would be n - 1 - d(v), which is odd. Thank You!
$endgroup$
– Haris
Jan 16 at 19:19
$begingroup$
Glad I could help. And I should have pointed out originally that your line of reasoning is correct.
$endgroup$
– Mike
Jan 16 at 19:26
add a comment |
1
$begingroup$
Oh, yeah, I see. Because the two sides have the same number of vertices, there could only be even number of vertices in G. So, degree of complement of every vertex would be n - 1 - d(v), which is odd. Thank You!
$endgroup$
– Haris
Jan 16 at 19:19
$begingroup$
Glad I could help. And I should have pointed out originally that your line of reasoning is correct.
$endgroup$
– Mike
Jan 16 at 19:26
1
1
$begingroup$
Oh, yeah, I see. Because the two sides have the same number of vertices, there could only be even number of vertices in G. So, degree of complement of every vertex would be n - 1 - d(v), which is odd. Thank You!
$endgroup$
– Haris
Jan 16 at 19:19
$begingroup$
Oh, yeah, I see. Because the two sides have the same number of vertices, there could only be even number of vertices in G. So, degree of complement of every vertex would be n - 1 - d(v), which is odd. Thank You!
$endgroup$
– Haris
Jan 16 at 19:19
$begingroup$
Glad I could help. And I should have pointed out originally that your line of reasoning is correct.
$endgroup$
– Mike
Jan 16 at 19:26
$begingroup$
Glad I could help. And I should have pointed out originally that your line of reasoning is correct.
$endgroup$
– Mike
Jan 16 at 19:26
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%2f3076152%2fif-g-is-a-bipartite-euler-and-hamiltonian-graph-prove-that-complement-of-g%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
