Mixing
Proof of Petersen's corollary
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I am trying to understand a proof to the following lemma:
Lemma: Every 3-regular graph with no cut edge has a perfect matching.
Proof: Let $S subseteq V(G)$. Let $H$ be a component of $Gsetminus S$ with $|H|$ odd. The number of edges between $S$ and $H$ cannot be 1, since $G$ has no cut edge. It also cannot be even, because then the sum of the vertex degrees in $H$ would be odd. Hence there are at least three edges from $H$ to $S$.
Since $G$ is 3-regular, each vertex of $S$ is incident to at most three edges between $S$ and $Gsetminus S$. Combining this fact with the previous paragraph, we have $3q(Gsetminus S) leq 3|S|$ and hence $q(Gsetminus S) leq |S|$ and the proof is concluded.
I cannot understand why the the number of edges between $S$ and $H$ cannot be even with the explanation of the proof. The sum of the vertex degrees in $H$ should be $3|H| -$ # edges leaving from $S$ to $Gsetminus S$. Is it because if it is even then the sum of vertex degrees wouldn't be a multiple of 3? Because in that case makes more sense.
graph-theory
asked Jul 31 at 13:30
dimkou
535
add a comment |Â
up vote
0
down vote
favorite
I am trying to understand a proof to the following lemma:
Lemma: Every 3-regular graph with no cut edge has a perfect matching.
Proof: Let $S subseteq V(G)$. Let $H$ be a component of $Gsetminus S$ with $|H|$ odd. The number of edges between $S$ and $H$ cannot be 1, since $G$ has no cut edge. It also cannot be even, because then the sum of the vertex degrees in $H$ would be odd. Hence there are at least three edges from $H$ to $S$.
Since $G$ is 3-regular, each vertex of $S$ is incident to at most three edges between $S$ and $Gsetminus S$. Combining this fact with the previous paragraph, we have $3q(Gsetminus S) leq 3|S|$ and hence $q(Gsetminus S) leq |S|$ and the proof is concluded.
I cannot understand why the the number of edges between $S$ and $H$ cannot be even with the explanation of the proof. The sum of the vertex degrees in $H$ should be $3|H| -$ # edges leaving from $S$ to $Gsetminus S$. Is it because if it is even then the sum of vertex degrees wouldn't be a multiple of 3? Because in that case makes more sense.
graph-theory
asked Jul 31 at 13:30
dimkou
535
1
If the number of edges was even then, since $|H|$ is odd, $3|H|-$ # edges would be odd, contradiction, since the sum of the degrees must be even.
– quasi
Jul 31 at 13:40
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am trying to understand a proof to the following lemma:
Lemma: Every 3-regular graph with no cut edge has a perfect matching.
Proof: Let $S subseteq V(G)$. Let $H$ be a component of $Gsetminus S$ with $|H|$ odd. The number of edges between $S$ and $H$ cannot be 1, since $G$ has no cut edge. It also cannot be even, because then the sum of the vertex degrees in $H$ would be odd. Hence there are at least three edges from $H$ to $S$.
Since $G$ is 3-regular, each vertex of $S$ is incident to at most three edges between $S$ and $Gsetminus S$. Combining this fact with the previous paragraph, we have $3q(Gsetminus S) leq 3|S|$ and hence $q(Gsetminus S) leq |S|$ and the proof is concluded.
I cannot understand why the the number of edges between $S$ and $H$ cannot be even with the explanation of the proof. The sum of the vertex degrees in $H$ should be $3|H| -$ # edges leaving from $S$ to $Gsetminus S$. Is it because if it is even then the sum of vertex degrees wouldn't be a multiple of 3? Because in that case makes more sense.
graph-theory
asked Jul 31 at 13:30
dimkou
535
I am trying to understand a proof to the following lemma:
Lemma: Every 3-regular graph with no cut edge has a perfect matching.
Proof: Let $S subseteq V(G)$. Let $H$ be a component of $Gsetminus S$ with $|H|$ odd. The number of edges between $S$ and $H$ cannot be 1, since $G$ has no cut edge. It also cannot be even, because then the sum of the vertex degrees in $H$ would be odd. Hence there are at least three edges from $H$ to $S$.
Since $G$ is 3-regular, each vertex of $S$ is incident to at most three edges between $S$ and $Gsetminus S$. Combining this fact with the previous paragraph, we have $3q(Gsetminus S) leq 3|S|$ and hence $q(Gsetminus S) leq |S|$ and the proof is concluded.
I cannot understand why the the number of edges between $S$ and $H$ cannot be even with the explanation of the proof. The sum of the vertex degrees in $H$ should be $3|H| -$ # edges leaving from $S$ to $Gsetminus S$. Is it because if it is even then the sum of vertex degrees wouldn't be a multiple of 3? Because in that case makes more sense.
graph-theory
asked Jul 31 at 13:30
dimkou
535
asked Jul 31 at 13:30
dimkou
535
asked Jul 31 at 13:30
dimkou
535
asked Jul 31 at 13:30
dimkou
535
535
1
If the number of edges was even then, since $|H|$ is odd, $3|H|-$ # edges would be odd, contradiction, since the sum of the degrees must be even.
– quasi
Jul 31 at 13:40
add a comment |Â
1
If the number of edges was even then, since $|H|$ is odd, $3|H|-$ # edges would be odd, contradiction, since the sum of the degrees must be even.
– quasi
Jul 31 at 13:40
1
1
If the number of edges was even then, since $|H|$ is odd, $3|H|-$ # edges would be odd, contradiction, since the sum of the degrees must be even.
– quasi
Jul 31 at 13:40
If the number of edges was even then, since $|H|$ is odd, $3|H|-$ # edges would be odd, contradiction, since the sum of the degrees must be even.
– quasi
Jul 31 at 13:40
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2868042%2fproof-of-petersens-corollary%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
If the number of edges was even then, since $|H|$ is odd, $3|H|-$ # edges would be odd, contradiction, since the sum of the degrees must be even.
– quasi
Jul 31 at 13:40