- #1
Superyoshiom
- 29
- 0
The problem is for us to consider a biconnected decomposition, and that proof for a graph, the degrees of all the vertices in a graph is even iff the degrees of all the vertices in all of its maximal biconnected components is even
For solving that if the degrees of all the vertices in the biconnected component were even then the degrees of all the vertices in the graph were even (first direction), my confusion is that if the degree of every vertex is even, we can't just connect the biconnected components together with one edge, because then the degree of the vertices would become odd.
Another issue I have is going the other direction, and proving that if the degrees of all the vertices in a graph were even, then the degrees of all the vertices in the maximal biconnected subgraphs are all even. Again, if I find a cut edge and remove it from the biconnected components, then the degrees of those vertices incident to the cut edge now become odd if they were originally even.
Am I missing something here? I was told that solving the proof in one direction would be trivial and solving it the other way would use induction, but I can't tell which is which.
For solving that if the degrees of all the vertices in the biconnected component were even then the degrees of all the vertices in the graph were even (first direction), my confusion is that if the degree of every vertex is even, we can't just connect the biconnected components together with one edge, because then the degree of the vertices would become odd.
Another issue I have is going the other direction, and proving that if the degrees of all the vertices in a graph were even, then the degrees of all the vertices in the maximal biconnected subgraphs are all even. Again, if I find a cut edge and remove it from the biconnected components, then the degrees of those vertices incident to the cut edge now become odd if they were originally even.
Am I missing something here? I was told that solving the proof in one direction would be trivial and solving it the other way would use induction, but I can't tell which is which.