We have a connected graph with $2n$ nodes. Prove that exist spanning subgraph each node with odd degree.
$begingroup$
We have a connected graph with $2n$ nodes. Prove that exsist spanning subgraph each node with odd degree.
Idea: Let $M$ be an adjacency matrix and work all over field $mathbb{Z}_2$. Then if $M$ is nonsingular we know that equation $$Mvec{s} = (1,1,1,....1,1)$$ has notrivial solution. Suppose set $S$ has incidence vector $vec{s}$. Then if for each node $a$ we color each edge in $N(a)cap S$ we win.
There are quite a few questions here. First, where did I use conectivity, second, is it $M$ really nonsingular and do we even need that and last, if all this is true does this aproach actually work?
Note: I already asked initaly question and did get an answer, so please answer just this.
linear-algebra combinatorics graph-theory algebraic-graph-theory algebraic-combinatorics
asked Dec 25 '18 at 20:41
Maria MazurMaria Mazur
50.3k1361126
$endgroup$
add a comment |
$begingroup$
We have a connected graph with $2n$ nodes. Prove that exsist spanning subgraph each node with odd degree.
Idea: Let $M$ be an adjacency matrix and work all over field $mathbb{Z}_2$. Then if $M$ is nonsingular we know that equation $$Mvec{s} = (1,1,1,....1,1)$$ has notrivial solution. Suppose set $S$ has incidence vector $vec{s}$. Then if for each node $a$ we color each edge in $N(a)cap S$ we win.
There are quite a few questions here. First, where did I use conectivity, second, is it $M$ really nonsingular and do we even need that and last, if all this is true does this aproach actually work?
Note: I already asked initaly question and did get an answer, so please answer just this.
linear-algebra combinatorics graph-theory algebraic-graph-theory algebraic-combinatorics
asked Dec 25 '18 at 20:41
Maria MazurMaria Mazur
50.3k1361126
$endgroup$
$begingroup$
Sorry I am a bit confused, do you want an answer to the initial quoted question or are you only asking about your approach?
$endgroup$
– Vincenzo
Dec 25 '18 at 21:34
$begingroup$
@Vincenzo second one.
$endgroup$
– Maria Mazur
Dec 25 '18 at 21:35
$begingroup$
I don't understand the question - clearly a simple path on $4$ vertices has an even number of vertices, but the only spanning subgraph (being the graph itself) has two vertices of even degree.
$endgroup$
– Math1000
Dec 25 '18 at 22:06
$begingroup$
Take a look here. math.stackexchange.com/questions/3047513/… @Math1000
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:08
1
$begingroup$
If you want a linear algebra solution, you should instead look at the incidence matrix of the graph and try to show that $Me={bf 1}$ has a solution. I do not know if this makes things any easier.
$endgroup$
– Mike Earnest
Dec 27 '18 at 17:44
add a comment |
$begingroup$
We have a connected graph with $2n$ nodes. Prove that exsist spanning subgraph each node with odd degree.
Idea: Let $M$ be an adjacency matrix and work all over field $mathbb{Z}_2$. Then if $M$ is nonsingular we know that equation $$Mvec{s} = (1,1,1,....1,1)$$ has notrivial solution. Suppose set $S$ has incidence vector $vec{s}$. Then if for each node $a$ we color each edge in $N(a)cap S$ we win.
There are quite a few questions here. First, where did I use conectivity, second, is it $M$ really nonsingular and do we even need that and last, if all this is true does this aproach actually work?
Note: I already asked initaly question and did get an answer, so please answer just this.
linear-algebra combinatorics graph-theory algebraic-graph-theory algebraic-combinatorics
asked Dec 25 '18 at 20:41
Maria MazurMaria Mazur
50.3k1361126
$endgroup$
We have a connected graph with $2n$ nodes. Prove that exsist spanning subgraph each node with odd degree.
Idea: Let $M$ be an adjacency matrix and work all over field $mathbb{Z}_2$. Then if $M$ is nonsingular we know that equation $$Mvec{s} = (1,1,1,....1,1)$$ has notrivial solution. Suppose set $S$ has incidence vector $vec{s}$. Then if for each node $a$ we color each edge in $N(a)cap S$ we win.
There are quite a few questions here. First, where did I use conectivity, second, is it $M$ really nonsingular and do we even need that and last, if all this is true does this aproach actually work?
Note: I already asked initaly question and did get an answer, so please answer just this.
linear-algebra combinatorics graph-theory algebraic-graph-theory algebraic-combinatorics
linear-algebra combinatorics graph-theory algebraic-graph-theory algebraic-combinatorics
asked Dec 25 '18 at 20:41
Maria MazurMaria Mazur
50.3k1361126
asked Dec 25 '18 at 20:41
Maria MazurMaria Mazur
50.3k1361126
edited Jan 23 at 20:09
Maria Mazur
asked Dec 25 '18 at 20:41
Maria MazurMaria Mazur
50.3k1361126
asked Dec 25 '18 at 20:41
Maria MazurMaria Mazur
50.3k1361126
asked Dec 25 '18 at 20:41
Maria MazurMaria Mazur
50.3k1361126
50.3k1361126
$begingroup$
Sorry I am a bit confused, do you want an answer to the initial quoted question or are you only asking about your approach?
$endgroup$
– Vincenzo
Dec 25 '18 at 21:34
$begingroup$
@Vincenzo second one.
$endgroup$
– Maria Mazur
Dec 25 '18 at 21:35
$begingroup$
I don't understand the question - clearly a simple path on $4$ vertices has an even number of vertices, but the only spanning subgraph (being the graph itself) has two vertices of even degree.
$endgroup$
– Math1000
Dec 25 '18 at 22:06
$begingroup$
Take a look here. math.stackexchange.com/questions/3047513/… @Math1000
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:08
1
$begingroup$
If you want a linear algebra solution, you should instead look at the incidence matrix of the graph and try to show that $Me={bf 1}$ has a solution. I do not know if this makes things any easier.
$endgroup$
– Mike Earnest
Dec 27 '18 at 17:44
add a comment |
$begingroup$
Sorry I am a bit confused, do you want an answer to the initial quoted question or are you only asking about your approach?
$endgroup$
– Vincenzo
Dec 25 '18 at 21:34
$begingroup$
@Vincenzo second one.
$endgroup$
– Maria Mazur
Dec 25 '18 at 21:35
$begingroup$
I don't understand the question - clearly a simple path on $4$ vertices has an even number of vertices, but the only spanning subgraph (being the graph itself) has two vertices of even degree.
$endgroup$
– Math1000
Dec 25 '18 at 22:06
$begingroup$
Take a look here. math.stackexchange.com/questions/3047513/… @Math1000
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:08
1
$begingroup$
If you want a linear algebra solution, you should instead look at the incidence matrix of the graph and try to show that $Me={bf 1}$ has a solution. I do not know if this makes things any easier.
$endgroup$
– Mike Earnest
Dec 27 '18 at 17:44
$begingroup$
Sorry I am a bit confused, do you want an answer to the initial quoted question or are you only asking about your approach?
$endgroup$
– Vincenzo
Dec 25 '18 at 21:34
$begingroup$
Sorry I am a bit confused, do you want an answer to the initial quoted question or are you only asking about your approach?
$endgroup$
– Vincenzo
Dec 25 '18 at 21:34
$begingroup$
@Vincenzo second one.
$endgroup$
– Maria Mazur
Dec 25 '18 at 21:35
$begingroup$
@Vincenzo second one.
$endgroup$
– Maria Mazur
Dec 25 '18 at 21:35
$begingroup$
I don't understand the question - clearly a simple path on $4$ vertices has an even number of vertices, but the only spanning subgraph (being the graph itself) has two vertices of even degree.
$endgroup$
– Math1000
Dec 25 '18 at 22:06
$begingroup$
I don't understand the question - clearly a simple path on $4$ vertices has an even number of vertices, but the only spanning subgraph (being the graph itself) has two vertices of even degree.
$endgroup$
– Math1000
Dec 25 '18 at 22:06
$begingroup$
Take a look here. math.stackexchange.com/questions/3047513/… @Math1000
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:08
$begingroup$
Take a look here. math.stackexchange.com/questions/3047513/… @Math1000
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:08
1
1
$begingroup$
If you want a linear algebra solution, you should instead look at the incidence matrix of the graph and try to show that $Me={bf 1}$ has a solution. I do not know if this makes things any easier.
$endgroup$
– Mike Earnest
Dec 27 '18 at 17:44
$begingroup$
If you want a linear algebra solution, you should instead look at the incidence matrix of the graph and try to show that $Me={bf 1}$ has a solution. I do not know if this makes things any easier.
$endgroup$
– Mike Earnest
Dec 27 '18 at 17:44
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
A base of the approach is any solution of the equation $Mvec{s} = (1,1,1,....1,1)$. But I don’t know how to show algebraically that it exists. In particular, it exists and unique provided the matrix $M$ is non-singular. Unfortunately, the adjacency matrix is singular for any graph which has two vertices with the same set of neighbors. For instance, for a cycle $C_4$ on four vertices. Also I remark that connectedness algebraically means that for each distinct indices $k,l$ there exists a power $M^k=|m_{ij}|$ such that $m_{i,j}>0$, but here we need to consider $M$ over $Bbb Z$, but not over $Bbb Z_2$.
answered Dec 25 '18 at 21:21
Alex RavskyAlex Ravsky
43.3k32583
$endgroup$
$begingroup$
Anyway, do you have a perhaps an idea how to atack this algebraicly
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:00
$begingroup$
You think this is hopless try with linear algebra?
$endgroup$
– Maria Mazur
Dec 26 '18 at 22:01
$begingroup$
@greedoid I rewrote my answer. Unfortunately, I don't know how to solve this problem algebraically. But I have to confess that although I have experience in graph and matrix theories, I'm ignoramus in algebraic graph theory. :-( So I put it to my ignored tags and I saw your question accidentally.
$endgroup$
– Alex Ravsky
Dec 30 '18 at 16:34
add a comment |
Your Answer
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%2f3052416%2fwe-have-a-connected-graph-with-2n-nodes-prove-that-exist-spanning-subgraph-ea%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$
A base of the approach is any solution of the equation $Mvec{s} = (1,1,1,....1,1)$. But I don’t know how to show algebraically that it exists. In particular, it exists and unique provided the matrix $M$ is non-singular. Unfortunately, the adjacency matrix is singular for any graph which has two vertices with the same set of neighbors. For instance, for a cycle $C_4$ on four vertices. Also I remark that connectedness algebraically means that for each distinct indices $k,l$ there exists a power $M^k=|m_{ij}|$ such that $m_{i,j}>0$, but here we need to consider $M$ over $Bbb Z$, but not over $Bbb Z_2$.
answered Dec 25 '18 at 21:21
Alex RavskyAlex Ravsky
43.3k32583
$endgroup$
$begingroup$
Anyway, do you have a perhaps an idea how to atack this algebraicly
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:00
$begingroup$
You think this is hopless try with linear algebra?
$endgroup$
– Maria Mazur
Dec 26 '18 at 22:01
$begingroup$
@greedoid I rewrote my answer. Unfortunately, I don't know how to solve this problem algebraically. But I have to confess that although I have experience in graph and matrix theories, I'm ignoramus in algebraic graph theory. :-( So I put it to my ignored tags and I saw your question accidentally.
$endgroup$
– Alex Ravsky
Dec 30 '18 at 16:34
add a comment |
$begingroup$
A base of the approach is any solution of the equation $Mvec{s} = (1,1,1,....1,1)$. But I don’t know how to show algebraically that it exists. In particular, it exists and unique provided the matrix $M$ is non-singular. Unfortunately, the adjacency matrix is singular for any graph which has two vertices with the same set of neighbors. For instance, for a cycle $C_4$ on four vertices. Also I remark that connectedness algebraically means that for each distinct indices $k,l$ there exists a power $M^k=|m_{ij}|$ such that $m_{i,j}>0$, but here we need to consider $M$ over $Bbb Z$, but not over $Bbb Z_2$.
answered Dec 25 '18 at 21:21
Alex RavskyAlex Ravsky
43.3k32583
$endgroup$
$begingroup$
Anyway, do you have a perhaps an idea how to atack this algebraicly
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:00
$begingroup$
You think this is hopless try with linear algebra?
$endgroup$
– Maria Mazur
Dec 26 '18 at 22:01
$begingroup$
@greedoid I rewrote my answer. Unfortunately, I don't know how to solve this problem algebraically. But I have to confess that although I have experience in graph and matrix theories, I'm ignoramus in algebraic graph theory. :-( So I put it to my ignored tags and I saw your question accidentally.
$endgroup$
– Alex Ravsky
Dec 30 '18 at 16:34
add a comment |
$begingroup$
A base of the approach is any solution of the equation $Mvec{s} = (1,1,1,....1,1)$. But I don’t know how to show algebraically that it exists. In particular, it exists and unique provided the matrix $M$ is non-singular. Unfortunately, the adjacency matrix is singular for any graph which has two vertices with the same set of neighbors. For instance, for a cycle $C_4$ on four vertices. Also I remark that connectedness algebraically means that for each distinct indices $k,l$ there exists a power $M^k=|m_{ij}|$ such that $m_{i,j}>0$, but here we need to consider $M$ over $Bbb Z$, but not over $Bbb Z_2$.
answered Dec 25 '18 at 21:21
Alex RavskyAlex Ravsky
43.3k32583
$endgroup$
A base of the approach is any solution of the equation $Mvec{s} = (1,1,1,....1,1)$. But I don’t know how to show algebraically that it exists. In particular, it exists and unique provided the matrix $M$ is non-singular. Unfortunately, the adjacency matrix is singular for any graph which has two vertices with the same set of neighbors. For instance, for a cycle $C_4$ on four vertices. Also I remark that connectedness algebraically means that for each distinct indices $k,l$ there exists a power $M^k=|m_{ij}|$ such that $m_{i,j}>0$, but here we need to consider $M$ over $Bbb Z$, but not over $Bbb Z_2$.
answered Dec 25 '18 at 21:21
Alex RavskyAlex Ravsky
43.3k32583
edited Dec 30 '18 at 16:34
answered Dec 25 '18 at 21:21
Alex RavskyAlex Ravsky
43.3k32583
answered Dec 25 '18 at 21:21
Alex RavskyAlex Ravsky
43.3k32583
answered Dec 25 '18 at 21:21
Alex RavskyAlex Ravsky
43.3k32583
43.3k32583
$begingroup$
Anyway, do you have a perhaps an idea how to atack this algebraicly
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:00
$begingroup$
You think this is hopless try with linear algebra?
$endgroup$
– Maria Mazur
Dec 26 '18 at 22:01
$begingroup$
@greedoid I rewrote my answer. Unfortunately, I don't know how to solve this problem algebraically. But I have to confess that although I have experience in graph and matrix theories, I'm ignoramus in algebraic graph theory. :-( So I put it to my ignored tags and I saw your question accidentally.
$endgroup$
– Alex Ravsky
Dec 30 '18 at 16:34
add a comment |
$begingroup$
Anyway, do you have a perhaps an idea how to atack this algebraicly
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:00
$begingroup$
You think this is hopless try with linear algebra?
$endgroup$
– Maria Mazur
Dec 26 '18 at 22:01
$begingroup$
@greedoid I rewrote my answer. Unfortunately, I don't know how to solve this problem algebraically. But I have to confess that although I have experience in graph and matrix theories, I'm ignoramus in algebraic graph theory. :-( So I put it to my ignored tags and I saw your question accidentally.
$endgroup$
– Alex Ravsky
Dec 30 '18 at 16:34
$begingroup$
Anyway, do you have a perhaps an idea how to atack this algebraicly
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:00
$begingroup$
Anyway, do you have a perhaps an idea how to atack this algebraicly
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:00
$begingroup$
You think this is hopless try with linear algebra?
$endgroup$
– Maria Mazur
Dec 26 '18 at 22:01
$begingroup$
You think this is hopless try with linear algebra?
$endgroup$
– Maria Mazur
Dec 26 '18 at 22:01
$begingroup$
@greedoid I rewrote my answer. Unfortunately, I don't know how to solve this problem algebraically. But I have to confess that although I have experience in graph and matrix theories, I'm ignoramus in algebraic graph theory. :-( So I put it to my ignored tags and I saw your question accidentally.
$endgroup$
– Alex Ravsky
Dec 30 '18 at 16:34
$begingroup$
@greedoid I rewrote my answer. Unfortunately, I don't know how to solve this problem algebraically. But I have to confess that although I have experience in graph and matrix theories, I'm ignoramus in algebraic graph theory. :-( So I put it to my ignored tags and I saw your question accidentally.
$endgroup$
– Alex Ravsky
Dec 30 '18 at 16:34
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%2f3052416%2fwe-have-a-connected-graph-with-2n-nodes-prove-that-exist-spanning-subgraph-ea%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$
Sorry I am a bit confused, do you want an answer to the initial quoted question or are you only asking about your approach?
$endgroup$
– Vincenzo
Dec 25 '18 at 21:34
$begingroup$
@Vincenzo second one.
$endgroup$
– Maria Mazur
Dec 25 '18 at 21:35
$begingroup$
I don't understand the question - clearly a simple path on $4$ vertices has an even number of vertices, but the only spanning subgraph (being the graph itself) has two vertices of even degree.
$endgroup$
– Math1000
Dec 25 '18 at 22:06
$begingroup$
Take a look here. math.stackexchange.com/questions/3047513/… @Math1000
$endgroup$
– Maria Mazur
Dec 25 '18 at 22:08
1
$begingroup$
If you want a linear algebra solution, you should instead look at the incidence matrix of the graph and try to show that $Me={bf 1}$ has a solution. I do not know if this makes things any easier.
$endgroup$
– Mike Earnest
Dec 27 '18 at 17:44