We have a connected graph with $2n$ nodes. Prove that exist spanning subgraph each node with odd degree.












2












$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







share|cite|improve this question











$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
















2












$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







share|cite|improve this question











$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














2












2








2





$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







share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 23 at 20:09







Maria Mazur

















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


















  • $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










1 Answer
1






active

oldest

votes


















1












$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$.






share|cite|improve this answer











$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












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
});


}
});














draft saved

draft discarded


















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









1












$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$.






share|cite|improve this answer











$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
















1












$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$.






share|cite|improve this answer











$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














1












1








1





$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$.






share|cite|improve this answer











$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$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 30 '18 at 16:34

























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


















  • $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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







-

Popular posts from this blog

mysqli_query(): Empty query in /home/lucindabrummitt/public_html/blog/wp-includes/wp-db.php on line 1924

Image
0 I just uploaded a new plugin to my wordpress site and I got this warning: mysqli_query(): Empty query in /home/lucindabrummitt/public_html/blog/wp-includes/wp-db.php on line 1924 Usually if I have a problem, I can find answers on google but this one seems pretty particular and I'm not finding any info on it except for this forum. I'm not terribly techie but if someone can tell me how to read this and how to change it I can follow directions pretty well. Thanks All! PS If I don't have the proper tags here could someone add the appropriate tags? php mysql wordpress share | improve this question asked Nov 16 '18 at 20:41 ...
Read more

How to change which sound is reproduced for terminal bell?

Image
3 Recently upgrade to 18.10 from 18.04, and using the terminal is becoming annoying: the new alert sound is a drip ( /usr/share/sounds/gnome/default/alerts/drip.ogg ), and the previous one is still located at ( /usr/share/sounds/ubuntu/stereo/bell.ogg ). My issue is that at the gnome-terminal, when autocompleting or pressing left BOTH sounds are reproduced, at the same time. I want to just have ubuntu/stereo/bell.ogg active, not both . At the moment I have been only able to reduce the volume of the alerts (but still both are played), or turn the alerts down (but I dislike both "solutions"). gnome-terminal 18.10 teminal-bell share | improve this question ...
Read more

Can I use Tabulator js library in my java Spring + Thymeleaf project?

Image
0 I want to add Tabulator js to my java project. I added tabulator.min.js, tabulator.min.css to resources folder. After that added to my html page these dependencies as recommending in readme.md. <link rel="stylesheet" th:href="@{/css/tabulator.min.css}"> <script type="text/javascript" th:src="@{/js/tabulator.min.js}"></script> Now my tables view all elements, that I have in the html page, but not correct. In the documentation of Tabulator is example how to create header and table, var table = new Tabulator("#example-table", { columns:[ {title:"Name", field:"name", sorter:"string", width:200, editor:true}, {title:"Age", field:"age", sorter:"...
Read more