I Question regarding degrees of a graph and its biconnected components

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.
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
the degrees of all the vertices in all of its maximal biconnected components is even
This is ambiguous. Is it considering the degree of a vertex within the maximal biconnected subgraph to which it belongs or its degree within the whole graph?
I suggest that the proposition is only true for one interpretation.
 
This is ambiguous. Is it considering the degree of a vertex within the maximal biconnected subgraph to which it belongs or its degree within the whole graph?
I suggest that the proposition is only true for one interpretation.
I admit it might have sounded a bit ambiguous, I've attached the problem here:
244791
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
That makes it clear that we are always concerned with the degree of the vertex in G. This is not how you seem to have interpreted it:
So then for one direction, if each of the biconnected components have all vertices of even degree, then the graph would then have all vertices of even degree since the graph is essentially just the union of all these components? I am assuming that's the trivial case.

Then for the inductive case the other way, I start off with a graph G with an even number of edges, then my assumption is to remove a vertex in the graph to see then if it creates two separate components, and if it does that would mean that:

1) There exists an articulation vertex so the graph isn't really biconnected
2) If all my vertices had even values, if I remove an articulation vertex, the edges incident to it would also be removed so the remaining vertices incident to those edges would have an odd degree since we removed one edge from each

Is my understanding there correct?
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
There exists an articulation vertex so the graph isn't really biconnected
The graph need not be biconnected. It has biconnected components.

But I made the mistake of not attempting to answer the question myself. Now that I have done so I believe the question statement is misleading and your original interpretation was correct.

So, returning to your confusion in post #1, you cannot connect two components with a single edge. That edge would then be another component, and it would have vertices that have an odd number of adjacent vertices within the component.
 
Last edited:
The graph need not be biconnected. It has biconnected components.
But I thought that the part that says: "Show that for graph G, ∀v ∈ V (G) : d(v) is even" means that all the vertices of G are even
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
But I thought that the part that says: "Show that for graph G, ∀v ∈ V (G) : d(v) is even" means that all the vertices of G are even
Yes, but G need not be biconnected.

Please see my edit to post #6
 
Yes, but G need not be biconnected.

Please see my edit to post #6
Alright then. In that case, how would I be able to prove that the graph would have all even degrees then, considering that it could have components in it that aren't necessarily biconnected or have even degrees?
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
Alright then. In that case, how would I be able to prove that the graph would have all even degrees then, considering that it could have components in it that aren't necessarily biconnected or have even degrees?
Its maximally biconnected components are biconnected by definition, but G as a whole is not biconnected unless it consists of a single such component.

E.g. G has six vertices as two separate triangles: each triangle is biconnected but G is not even connected,
Now join the triangles with an edge. G now has three maximally biconnected components, the new edge being one of them. Within the original two components all vertices are even degree (i.e. within the triangles) but the added edge component has two vertices of degree 1.
Now collapse that edge so we have only five vertices, one being shared by the two triangles. There are two maximally biconnected components again, and each vertex has even degree both within each component to which it belongs and in G as a whole.

Let's start with the easier direction. Show that if a vertex has even degree within each maximally biconnected component to which it belongs then it has even degree in G.
 
Its maximally biconnected components are biconnected by definition, but G as a whole is not biconnected unless it consists of a single such component.

E.g. G has six vertices as two separate triangles: each triangle is biconnected but G is not even connected,
Now join the triangles with an edge. G now has three maximally biconnected components, the new edge being one of them. Within the original two components all vertices are even degree (i.e. within the triangles) but the added edge component has two vertices of degree 1.
Now collapse that edge so we have only five vertices, one being shared by the two triangles. There are two maximally biconnected components again, and each vertex has even degree both within each component to which it belongs and in G as a whole.

Let's start with the easier direction. Show that if a vertex has even degree within each maximally biconnected component to which it belongs then it has even degree in G.
This part is where I'm having trouble though, with the traingle example you just provided, as two components all six vertices would have degree 2; however if we connected them in G, then the two vertices from the traingles used for that edge would then have degree 3
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
This part is where I'm having trouble though, with the traingle example you just provided, as two components all six vertices would have degree 2; however if we connected them in G, then the two vertices from the traingles used for that edge would then have degree 3
Right, but that is not a counterexample to the proposition you are asked to prove.
The graph G contains vertices of odd degree, so there is no claim that the all components have all vertices as even degree; there exists a component (the added edge) that has vertices of odd degree within it, so there is no claim that all vertices should have even degree in G.
 
Right, but that is not a counterexample to the proposition you are asked to prove.
The graph G contains vertices of odd degree, so there is no claim that the all components have all vertices as even degree; there exists a component (the added edge) that has vertices of odd degree within it, so there is no claim that all vertices should have even degree in G.
If G doesn't have to have all of it's vertices even, when the problem states: "t for graph G, ∀v ∈ V (G) : d(v) is even iff for every maximal biconnected component Bi ∈ G, ∀u ∈ V (Bi) : d(u) is even" that v and u refer to the same vertices?

In that case, the first direction (Show that if a vertex has even degree within each maximally biconnected component to which it belongs then it has even degree in G.) could be trivially proven because G is just a union of all the biconnected components? I'm still unsure however, of this:
244805

In G, which is just the components by themselves, the two top nodes on each component has degree two; however if I had an edge between them their degree becomes three, so in the full graph their degree becomes odd. The two triangles are still the only maximal biconnected components though, because if we combine one triangle and the edge we can remove the edge and disconnect the graph.
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
If G doesn't have to have all of it's vertices even
For brevity I'll abbreviate maximally biconnected component to "mbc".
These are the two things you are to prove:
A) if G is such that each of its vertices is even and C is a mbc of G then every vertex in C is adjacent to an even number of other vertices in C
B) if for every mbc C in G each of its vertices is adjacent to an even number of other vertices in C then all of G's vertices are even.
In your construction in post #11, when you added the edge, G had two vertices of odd degree, so was not a counterexample to A because it does not satisfy the condition. Likewise it is not a counterexample to B because that added edge is a mbc with two vertices of degree 1 within it, so does not meet the condition for B.

could be trivially proven because G is just a union of all the biconnected components?
Not so fast. Suppose v is an articulation vertex in the two mbc C and D. It may have even degree in each, but does that prove it has even degree in G? Can any of its incident edges be in both mbcs?
if I had an edge between them their degree becomes three, so in the full graph their degree becomes odd. The two triangles are still the only maximal biconnected components though
This is what you are not getting. The added edge, together with its incident vertices, is another mbc.
 
For brevity I'll abbreviate maximally biconnected component to "mbc".
These are the two things you are to prove:
A) if G is such that each of its vertices is even and C is a mbc of G then every vertex in C is adjacent to an even number of other vertices in C
B) if for every mbc C in G each of its vertices is adjacent to an even number of other vertices in C then all of G's vertices are even.
In your construction in post #11, when you added the edge, G had two vertices of odd degree, so was not a counterexample to A because it does not satisfy the condition. Likewise it is not a counterexample to B because that added edge is a mbc with two vertices of degree 1 within it, so does not meet the condition for B.


Not so fast. Suppose v is an articulation vertex in the two mbc C and D. It may have even degree in each, but does that prove it has even degree in G? Can any of its incident edges be in both mbcs?

This is what you are not getting. The added edge, together with its incident vertices, is another mbc.
I think I better understand now. The G' graph I created wouldn't exist because those two vertices and the line across from them is their own maximal biconnected component on it's own. However, is it true that two vertices and an edge between them is biconnected, since removing one vertex removes the edge altogether.

If that is the case then, I would be able to see that if all maximal biconnected compoments had all even vertices, we would not be able to attach to them only 1 edge since that would mean that the other vertices incident on that edge would have an odd degree. We also couldn't have a single edge connecting two mbcs for that reason.

In that case, I just need to show that there are no odd degrees in the rest of the graph. Is the way to do that is to say that if two vertices and an edge connecting them is a mbc, then we literally could not create any odd number of vertices coming some a single vertex because the pairs of vertices incident to all of those odd number of edges are all their own mcbs and thus must have even degree?
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
Yes.

That does not sound right. Please explain your logic in more detail.
My logic was that for a vertex to have any degree, it must have an edge connecting it to another vertex (I assume that this graph is simple). But an edge is its own mbc, so then the number of vertices coming from any edge in G must be itself even, since connected graphs are just a union of mbcs(?)
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
number of vertices coming from any edge in G
Did you mean number of edges from a vertex?
But an edge is its own mbc
Only if there is no other path connecting its endpoints.
connected graphs are just a union of mbcs(?)
Too vague.
As I mentioned, the key for this (the easier) part is to show that if a vertex belongs to two or more mbc then its incident edges are partitioned between them. I.e. an edge cannot belong to two mbc.
 
As I mentioned, the key for this (the easier) part is to show that if a vertex belongs to two or more mbc then its incident edges are partitioned between them. I.e. an edge cannot belong to two mbc.
Ok, so an edge cannot belong to two mbc because that would mean that the degree of the two incident vertices of the two mbc's would be odd. But if we connected edges so that we had an even number of edges from each vertex of the two mbc's that connected them both, then that makes a contradiction since that whole thing (the two mbc's plus the edges connecting them) would form its own maximal biconnected component since we could remove one of the connecting edges and the whole thing would still be connected.
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
Ok, so an edge cannot belong to two mbc because that would mean that the degree of the two incident vertices of the two mbc's would be odd.
I don't see why it would mean that.
Forget about odd and even degrees for the moment. Is it possible for an edge to be in two mbc? What would happen if you were to delete one of its vertices?
 
I don't see why it would mean that.
Forget about odd and even degrees for the moment. Is it possible for an edge to be in two mbc? What would happen if you were to delete one of its vertices?
I don't think an edge can be in two mbc's. If an edge is part of an mbc, so if we remove it from the mbc it should still be connected if we remove one of its vertices. However, if that edge is connecting two mbcs, A and B, if we remove a vertex of that edge in A, does that disconnect A? Would it violate the properties of a maximal biconnected component?
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
if that edge is connecting two mbcs
No, edges do not connect mbcs. Vertices connect mbcs by being members of them.
Consider an edge. It must belong to (at least one) mbc, and if an edge belongs to an mbc what can you say about its endpoints and that mbc?
 
No, edges do not connect mbcs. Vertices connect mbcs by being members of them.
Consider an edge. It must belong to (at least one) mbc, and if an edge belongs to an mbc what can you say about its endpoints and that mbc?
The endpoints of an edge if it's in an mbc have to be incident to two or more edges including that edge. So if we remove that endpoint, we'd be removing more than two edges from the mbc.
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,238
4,558
The endpoints of an edge if it's in an mbc have to be incident to two or more edges including that edge. So if we remove that endpoint, we'd be removing more than two edges from the mbc.
My question was not clear enough, I know... what I was looking for is that if an edge belongs to an mbc then there must be a second path between its endpoints within the mbc, right?
Now can you show that an edge cannot belong to two mbcs? Note that you have to use the maximality part.
 

Want to reply to this thread?

"Question regarding degrees of a graph and its biconnected components" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top