If $|E(G)| geq |V(G)| +4,$ then G contains two edge-disjoint cycles [closed]
$begingroup$
This exercise is on the book Graph theory with Application by Bonty and Murty (1.7.6). I'm studying for a final test and I can't complete this prove.
I know how to do construct that graph but I don't know if that proves it for all the cases.
graph-theory
edited Jan 14 at 18:31
Maria Mazur
48.3k1260121
asked Jan 14 at 15:26
John HernandezJohn Hernandez
205
$endgroup$
closed as off-topic by Namaste, Adrian Keister, Eevee Trainer, Cesareo, mrtaurho Jan 15 at 5:49
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, Adrian Keister, Eevee Trainer, Cesareo, mrtaurho
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
This exercise is on the book Graph theory with Application by Bonty and Murty (1.7.6). I'm studying for a final test and I can't complete this prove.
I know how to do construct that graph but I don't know if that proves it for all the cases.
graph-theory
edited Jan 14 at 18:31
Maria Mazur
48.3k1260121
asked Jan 14 at 15:26
John HernandezJohn Hernandez
205
$endgroup$
closed as off-topic by Namaste, Adrian Keister, Eevee Trainer, Cesareo, mrtaurho Jan 15 at 5:49
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, Adrian Keister, Eevee Trainer, Cesareo, mrtaurho
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
I have a proof of this, but it is a rather ugly case analysis. I hope someone provides a more elegant proof. If not, I will post it as an answer.
$endgroup$
– Leen Droogendijk
Jan 14 at 15:45
add a comment |
$begingroup$
This exercise is on the book Graph theory with Application by Bonty and Murty (1.7.6). I'm studying for a final test and I can't complete this prove.
I know how to do construct that graph but I don't know if that proves it for all the cases.
graph-theory
edited Jan 14 at 18:31
Maria Mazur
48.3k1260121
asked Jan 14 at 15:26
John HernandezJohn Hernandez
205
$endgroup$
This exercise is on the book Graph theory with Application by Bonty and Murty (1.7.6). I'm studying for a final test and I can't complete this prove.
I know how to do construct that graph but I don't know if that proves it for all the cases.
graph-theory
graph-theory
edited Jan 14 at 18:31
Maria Mazur
48.3k1260121
asked Jan 14 at 15:26
John HernandezJohn Hernandez
205
edited Jan 14 at 18:31
Maria Mazur
48.3k1260121
asked Jan 14 at 15:26
John HernandezJohn Hernandez
205
edited Jan 14 at 18:31
Maria Mazur
48.3k1260121
edited Jan 14 at 18:31
Maria Mazur
48.3k1260121
edited Jan 14 at 18:31
Maria Mazur
48.3k1260121
48.3k1260121
asked Jan 14 at 15:26
John HernandezJohn Hernandez
205
asked Jan 14 at 15:26
John HernandezJohn Hernandez
205
asked Jan 14 at 15:26
John HernandezJohn Hernandez
205
205
closed as off-topic by Namaste, Adrian Keister, Eevee Trainer, Cesareo, mrtaurho Jan 15 at 5:49
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, Adrian Keister, Eevee Trainer, Cesareo, mrtaurho
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Namaste, Adrian Keister, Eevee Trainer, Cesareo, mrtaurho Jan 15 at 5:49
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Namaste, Adrian Keister, Eevee Trainer, Cesareo, mrtaurho
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
I have a proof of this, but it is a rather ugly case analysis. I hope someone provides a more elegant proof. If not, I will post it as an answer.
$endgroup$
– Leen Droogendijk
Jan 14 at 15:45
add a comment |
$begingroup$
I have a proof of this, but it is a rather ugly case analysis. I hope someone provides a more elegant proof. If not, I will post it as an answer.
$endgroup$
– Leen Droogendijk
Jan 14 at 15:45
$begingroup$
I have a proof of this, but it is a rather ugly case analysis. I hope someone provides a more elegant proof. If not, I will post it as an answer.
$endgroup$
– Leen Droogendijk
Jan 14 at 15:45
$begingroup$
I have a proof of this, but it is a rather ugly case analysis. I hope someone provides a more elegant proof. If not, I will post it as an answer.
$endgroup$
– Leen Droogendijk
Jan 14 at 15:45
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
We can begin by making a few simplifications.
If $|E(G)| > |V(G)| + 4$, we can delete the extra edges to get a graph $G'$ with $|E(G')| = |V(G')|+4$. If there are two edge-disjoint cycles in $G'$, they still exist in $G$. So we can assume that equality holds.
If $G$ has a vertex of degree $1$, then we can delete that vertex and the edge out of it. The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $2$.
Similarly, if $G$ has a vertex of degree $2$, then we can delete that vertex and the edges out of it, but connect its neighbors by an edge directly. (This might create a multigraph out of a simple graph.) The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $3$.
In a graph with minimum degree $3$, $|E(G)| ge frac32 |V(G)|$; when $|E(G)| = |V(G)|+4$, we conclude that $|V(G)| + 4 ge frac32 |V(G)|$, so $|V(G)| le 8$.
If $G$ has no cycles of length $4$ or shorter (which means in particular that it has no cycles of length $1$ or $2$, so it is a simple graph), then take an arbitrary vertex $v$ and three of its neighbors $w_1, w_2, w_3$; those neighbors must have at least $6$ more neighbors of their own, distinct from each other and from $v$, giving us at least $10$ vertices, contradicting $|V(G)| le 8$.
But if $G$ has a cycle of length $4$ or shorter, then we can delete all edges in that cycle; the remaining graph $G'$ still has $|E(G')| ge |V(G')|$, so it contains a second cycle, which is disjoint from the first. This gives us two edge-disjoint cycles in $G$, completing the proof.
answered Jan 14 at 18:21
Misha LavrovMisha Lavrov
47.8k657107
$endgroup$
$begingroup$
Very nice Misha! This idea of reducing things is great. Any whay I was thinking about Nash-Williams theorem but...
$endgroup$
– Maria Mazur
Jan 14 at 19:11
$begingroup$
@Misha Lavrov you need to consider the case when you end up with a multigraph. Otherwise you cannot make some of the claims you made later(ie number of neighbours). It is technical, but important.
$endgroup$
– hbm
Jan 14 at 23:31
1
$begingroup$
@hbm In the case where $G$ has no cycles of length $4$ or shorter, it is automatically simple: a loop is a cycle of length $1$ and a pair of parallel edges is a cycle of length $2$. (And if we undo the smoothing operations that got rid of degree-$2$ vertices, such short cycles expand into perfectly good cycles of length $3$ or more.)
$endgroup$
– Misha Lavrov
Jan 14 at 23:46
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We can begin by making a few simplifications.
If $|E(G)| > |V(G)| + 4$, we can delete the extra edges to get a graph $G'$ with $|E(G')| = |V(G')|+4$. If there are two edge-disjoint cycles in $G'$, they still exist in $G$. So we can assume that equality holds.
If $G$ has a vertex of degree $1$, then we can delete that vertex and the edge out of it. The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $2$.
Similarly, if $G$ has a vertex of degree $2$, then we can delete that vertex and the edges out of it, but connect its neighbors by an edge directly. (This might create a multigraph out of a simple graph.) The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $3$.
In a graph with minimum degree $3$, $|E(G)| ge frac32 |V(G)|$; when $|E(G)| = |V(G)|+4$, we conclude that $|V(G)| + 4 ge frac32 |V(G)|$, so $|V(G)| le 8$.
If $G$ has no cycles of length $4$ or shorter (which means in particular that it has no cycles of length $1$ or $2$, so it is a simple graph), then take an arbitrary vertex $v$ and three of its neighbors $w_1, w_2, w_3$; those neighbors must have at least $6$ more neighbors of their own, distinct from each other and from $v$, giving us at least $10$ vertices, contradicting $|V(G)| le 8$.
But if $G$ has a cycle of length $4$ or shorter, then we can delete all edges in that cycle; the remaining graph $G'$ still has $|E(G')| ge |V(G')|$, so it contains a second cycle, which is disjoint from the first. This gives us two edge-disjoint cycles in $G$, completing the proof.
answered Jan 14 at 18:21
Misha LavrovMisha Lavrov
47.8k657107
$endgroup$
$begingroup$
Very nice Misha! This idea of reducing things is great. Any whay I was thinking about Nash-Williams theorem but...
$endgroup$
– Maria Mazur
Jan 14 at 19:11
$begingroup$
@Misha Lavrov you need to consider the case when you end up with a multigraph. Otherwise you cannot make some of the claims you made later(ie number of neighbours). It is technical, but important.
$endgroup$
– hbm
Jan 14 at 23:31
1
$begingroup$
@hbm In the case where $G$ has no cycles of length $4$ or shorter, it is automatically simple: a loop is a cycle of length $1$ and a pair of parallel edges is a cycle of length $2$. (And if we undo the smoothing operations that got rid of degree-$2$ vertices, such short cycles expand into perfectly good cycles of length $3$ or more.)
$endgroup$
– Misha Lavrov
Jan 14 at 23:46
add a comment |
$begingroup$
We can begin by making a few simplifications.
If $|E(G)| > |V(G)| + 4$, we can delete the extra edges to get a graph $G'$ with $|E(G')| = |V(G')|+4$. If there are two edge-disjoint cycles in $G'$, they still exist in $G$. So we can assume that equality holds.
If $G$ has a vertex of degree $1$, then we can delete that vertex and the edge out of it. The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $2$.
Similarly, if $G$ has a vertex of degree $2$, then we can delete that vertex and the edges out of it, but connect its neighbors by an edge directly. (This might create a multigraph out of a simple graph.) The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $3$.
In a graph with minimum degree $3$, $|E(G)| ge frac32 |V(G)|$; when $|E(G)| = |V(G)|+4$, we conclude that $|V(G)| + 4 ge frac32 |V(G)|$, so $|V(G)| le 8$.
If $G$ has no cycles of length $4$ or shorter (which means in particular that it has no cycles of length $1$ or $2$, so it is a simple graph), then take an arbitrary vertex $v$ and three of its neighbors $w_1, w_2, w_3$; those neighbors must have at least $6$ more neighbors of their own, distinct from each other and from $v$, giving us at least $10$ vertices, contradicting $|V(G)| le 8$.
But if $G$ has a cycle of length $4$ or shorter, then we can delete all edges in that cycle; the remaining graph $G'$ still has $|E(G')| ge |V(G')|$, so it contains a second cycle, which is disjoint from the first. This gives us two edge-disjoint cycles in $G$, completing the proof.
answered Jan 14 at 18:21
Misha LavrovMisha Lavrov
47.8k657107
$endgroup$
$begingroup$
Very nice Misha! This idea of reducing things is great. Any whay I was thinking about Nash-Williams theorem but...
$endgroup$
– Maria Mazur
Jan 14 at 19:11
$begingroup$
@Misha Lavrov you need to consider the case when you end up with a multigraph. Otherwise you cannot make some of the claims you made later(ie number of neighbours). It is technical, but important.
$endgroup$
– hbm
Jan 14 at 23:31
1
$begingroup$
@hbm In the case where $G$ has no cycles of length $4$ or shorter, it is automatically simple: a loop is a cycle of length $1$ and a pair of parallel edges is a cycle of length $2$. (And if we undo the smoothing operations that got rid of degree-$2$ vertices, such short cycles expand into perfectly good cycles of length $3$ or more.)
$endgroup$
– Misha Lavrov
Jan 14 at 23:46
add a comment |
$begingroup$
We can begin by making a few simplifications.
If $|E(G)| > |V(G)| + 4$, we can delete the extra edges to get a graph $G'$ with $|E(G')| = |V(G')|+4$. If there are two edge-disjoint cycles in $G'$, they still exist in $G$. So we can assume that equality holds.
If $G$ has a vertex of degree $1$, then we can delete that vertex and the edge out of it. The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $2$.
Similarly, if $G$ has a vertex of degree $2$, then we can delete that vertex and the edges out of it, but connect its neighbors by an edge directly. (This might create a multigraph out of a simple graph.) The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $3$.
In a graph with minimum degree $3$, $|E(G)| ge frac32 |V(G)|$; when $|E(G)| = |V(G)|+4$, we conclude that $|V(G)| + 4 ge frac32 |V(G)|$, so $|V(G)| le 8$.
If $G$ has no cycles of length $4$ or shorter (which means in particular that it has no cycles of length $1$ or $2$, so it is a simple graph), then take an arbitrary vertex $v$ and three of its neighbors $w_1, w_2, w_3$; those neighbors must have at least $6$ more neighbors of their own, distinct from each other and from $v$, giving us at least $10$ vertices, contradicting $|V(G)| le 8$.
But if $G$ has a cycle of length $4$ or shorter, then we can delete all edges in that cycle; the remaining graph $G'$ still has $|E(G')| ge |V(G')|$, so it contains a second cycle, which is disjoint from the first. This gives us two edge-disjoint cycles in $G$, completing the proof.
answered Jan 14 at 18:21
Misha LavrovMisha Lavrov
47.8k657107
$endgroup$
We can begin by making a few simplifications.
If $|E(G)| > |V(G)| + 4$, we can delete the extra edges to get a graph $G'$ with $|E(G')| = |V(G')|+4$. If there are two edge-disjoint cycles in $G'$, they still exist in $G$. So we can assume that equality holds.
If $G$ has a vertex of degree $1$, then we can delete that vertex and the edge out of it. The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $2$.
Similarly, if $G$ has a vertex of degree $2$, then we can delete that vertex and the edges out of it, but connect its neighbors by an edge directly. (This might create a multigraph out of a simple graph.) The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $3$.
In a graph with minimum degree $3$, $|E(G)| ge frac32 |V(G)|$; when $|E(G)| = |V(G)|+4$, we conclude that $|V(G)| + 4 ge frac32 |V(G)|$, so $|V(G)| le 8$.
If $G$ has no cycles of length $4$ or shorter (which means in particular that it has no cycles of length $1$ or $2$, so it is a simple graph), then take an arbitrary vertex $v$ and three of its neighbors $w_1, w_2, w_3$; those neighbors must have at least $6$ more neighbors of their own, distinct from each other and from $v$, giving us at least $10$ vertices, contradicting $|V(G)| le 8$.
But if $G$ has a cycle of length $4$ or shorter, then we can delete all edges in that cycle; the remaining graph $G'$ still has $|E(G')| ge |V(G')|$, so it contains a second cycle, which is disjoint from the first. This gives us two edge-disjoint cycles in $G$, completing the proof.
answered Jan 14 at 18:21
Misha LavrovMisha Lavrov
47.8k657107
edited Jan 14 at 23:46
answered Jan 14 at 18:21
Misha LavrovMisha Lavrov
47.8k657107
answered Jan 14 at 18:21
Misha LavrovMisha Lavrov
47.8k657107
answered Jan 14 at 18:21
Misha LavrovMisha Lavrov
47.8k657107
47.8k657107
$begingroup$
Very nice Misha! This idea of reducing things is great. Any whay I was thinking about Nash-Williams theorem but...
$endgroup$
– Maria Mazur
Jan 14 at 19:11
$begingroup$
@Misha Lavrov you need to consider the case when you end up with a multigraph. Otherwise you cannot make some of the claims you made later(ie number of neighbours). It is technical, but important.
$endgroup$
– hbm
Jan 14 at 23:31
1
$begingroup$
@hbm In the case where $G$ has no cycles of length $4$ or shorter, it is automatically simple: a loop is a cycle of length $1$ and a pair of parallel edges is a cycle of length $2$. (And if we undo the smoothing operations that got rid of degree-$2$ vertices, such short cycles expand into perfectly good cycles of length $3$ or more.)
$endgroup$
– Misha Lavrov
Jan 14 at 23:46
add a comment |
$begingroup$
Very nice Misha! This idea of reducing things is great. Any whay I was thinking about Nash-Williams theorem but...
$endgroup$
– Maria Mazur
Jan 14 at 19:11
$begingroup$
@Misha Lavrov you need to consider the case when you end up with a multigraph. Otherwise you cannot make some of the claims you made later(ie number of neighbours). It is technical, but important.
$endgroup$
– hbm
Jan 14 at 23:31
1
$begingroup$
@hbm In the case where $G$ has no cycles of length $4$ or shorter, it is automatically simple: a loop is a cycle of length $1$ and a pair of parallel edges is a cycle of length $2$. (And if we undo the smoothing operations that got rid of degree-$2$ vertices, such short cycles expand into perfectly good cycles of length $3$ or more.)
$endgroup$
– Misha Lavrov
Jan 14 at 23:46
$begingroup$
Very nice Misha! This idea of reducing things is great. Any whay I was thinking about Nash-Williams theorem but...
$endgroup$
– Maria Mazur
Jan 14 at 19:11
$begingroup$
Very nice Misha! This idea of reducing things is great. Any whay I was thinking about Nash-Williams theorem but...
$endgroup$
– Maria Mazur
Jan 14 at 19:11
$begingroup$
@Misha Lavrov you need to consider the case when you end up with a multigraph. Otherwise you cannot make some of the claims you made later(ie number of neighbours). It is technical, but important.
$endgroup$
– hbm
Jan 14 at 23:31
$begingroup$
@Misha Lavrov you need to consider the case when you end up with a multigraph. Otherwise you cannot make some of the claims you made later(ie number of neighbours). It is technical, but important.
$endgroup$
– hbm
Jan 14 at 23:31
1
1
$begingroup$
@hbm In the case where $G$ has no cycles of length $4$ or shorter, it is automatically simple: a loop is a cycle of length $1$ and a pair of parallel edges is a cycle of length $2$. (And if we undo the smoothing operations that got rid of degree-$2$ vertices, such short cycles expand into perfectly good cycles of length $3$ or more.)
$endgroup$
– Misha Lavrov
Jan 14 at 23:46
$begingroup$
@hbm In the case where $G$ has no cycles of length $4$ or shorter, it is automatically simple: a loop is a cycle of length $1$ and a pair of parallel edges is a cycle of length $2$. (And if we undo the smoothing operations that got rid of degree-$2$ vertices, such short cycles expand into perfectly good cycles of length $3$ or more.)
$endgroup$
– Misha Lavrov
Jan 14 at 23:46
add a comment |
$begingroup$
I have a proof of this, but it is a rather ugly case analysis. I hope someone provides a more elegant proof. If not, I will post it as an answer.
$endgroup$
– Leen Droogendijk
Jan 14 at 15:45