I Question regarding degrees of a graph and its biconnected components

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.
I think an edge cannot belong to two mbc's because every vertex on an mbc needs two paths to that vertex, so we'd need to have at least two edges connecting an mbc which would just make those two mbc's one maximal component and makes a violation?
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,196
4,540
I think an edge cannot belong to two mbc's because every vertex on an mbc needs two paths to that vertex, so we'd need to have at least two edges connecting an mbc which would just make those two mbc's one maximal component and makes a violation?
I think you have the idea, but your wording is a little off. It will be a lot clearer if we assign labels to the entities being discussed.
Let e=(u,v) be an edge in an mbc C. For any other vertex w in C there must be a path to u that does not use v and one to v that does not use u.
If the edge belongs to a second mbc, D, then the same is true for any vertex w' in that. Now suppose we remove any one vertex of G.
Can you show there must still be a path from w to w'
 
I think you have the idea, but your wording is a little off. It will be a lot clearer if we assign labels to the entities being discussed.
Let e=(u,v) be an edge in an mbc C. For any other vertex w in C there must be a path to u that does not use v and one to v that does not use u.
If the edge belongs to a second mbc, D, then the same is true for any vertex w' in that. Now suppose we remove any one vertex of G.
Can you show there must still be a path from w to w'
I would say that there is still a path, because since we have at least two vertices that can reach u and two that can reach v, removing only one vertex can remove at most one path to either u and v, so there is still a way to get from w to w'
 
vertices? You mean paths?

Or remove u or v.
I was studying for my class a bit today and came across this video explaining that all the vertices in a graph have even degrees if and only if there is a cycle decomposition of that graph. I assume that cycles can be biconnected components because similar to mbc's, if we remove one edge, the component remains connected.


I was wondering then, if I can utilize the logic in this video in a similar way:

1) If for every maximal biconnected component in G, they all have even degrees of vertices that are even, then the vertices of G are even.

If all the vertices of the mbc's are even then there must exist in there a cycle (since by definition, if a graph has vertices of only even degrees it must form a cycle). We can then take any vertex in the graph; it's isolated it'd have degree of 0 which still works as even, or if it is an mcb, then it is even because for every time t it enters a vertex v inside of the mcb it must exit as well so it has degree 2t.

2) If all the vertices of G are even then its maximal biconnected components also have all vertices of even degrees.

The problem states that we have a biconnectivity decomposition, so I'm assuming that every component of G's deocomposition is a biconnected one then. For the base case I could just use the trivial case of 1 vertex having degree 0 as would its decomposition, and then for the inductive case I'd just say that if G is a collection of biconnected components with even degrees, and that all connected graphs with even degrees are cycles, and so if a graph like that exists for k edges, then all the degrees in the graph would have to be even, then if we remove an even number of edges, we can just remove a cycle, and that would still make G have all even degrees.
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,196
4,540
If all the vertices of the mbc's are even then there must exist in there a cycle
You really must try to be less vague. Must exist in where? If you mean within an mbc then you should have written "If all the vertices of an mbc ..."
And mere existence of a cycle isn't going to get you far. It is crucial (if using this approach) that the set of edges can be decomposed into disjoint cycles.
The rest of that paragraph doesn't seem to go anywhere. How does it lead to all the vertices in G being even?
all connected graphs with even degrees are cycles
No, they need not be cycles but can be decomposed into a disjoint union of cycles.
if G is a collection of biconnected components with even degrees, ....
then if we remove an even number of edges
You are taking G to be a graph for which the proposition is true. The inductive step should be showing it is true for some larger graph. The right way is to start with something like "suppose the proposition is true for all graphs up some number of (vertices or edges or mbcs ... probably doesn’t matter which you choose). Let G be a graph with one more but does not satisfy the proposition ". Then you consider removing something from G such that the reduced graph doesn’t satisfy it either.
 
You really must try to be less vague. Must exist in where? If you mean within an mbc then you should have written "If all the vertices of an mbc ..."
And mere existence of a cycle isn't going to get you far. It is crucial (if using this approach) that the set of edges can be decomposed into disjoint cycles.
The rest of that paragraph doesn't seem to go anywhere. How does it lead to all the vertices in G being even?

No, they need not be cycles but can be decomposed into a disjoint union of cycles.

You are taking G to be a graph for which the proposition is true. The inductive step should be showing it is true for some larger graph. The right way is to start with something like "suppose the proposition is true for all graphs up some number of (vertices or edges or mbcs ... probably doesn’t matter which you choose). Let G be a graph with one more but does not satisfy the proposition ". Then you consider removing something from G such that the reduced graph doesn’t satisfy it either.
Honestly the more and more I think about this problem the more confusing it gets.

If the graph G has all even vertices and we want to then show its maximal biconnected components have all of their vertex as even degrees, then I guess that since you have an even graph then every vertex must have an edge going in and going out of it which means that either G would be a collection of cycles or a collection of subgraphs that decompose to cycles, or just 1 vertex with no edges, which I think still counts as an mbc, and all cycles are also biconnected bcause there exists in them no articulation vertex. So I think that counts for one direction.

If the mbc's of the graph have all even degrees and we want to prove that then G is an even graph. I guess maybe just start with a case where we have two disconnected mcb's which counts as a graph that satisfies these conditions. Then we could add an edge to connect them, but this would violate both the graph being even and the mcb of that one connecting edge being even. So we'd need to add at least one more edge to connect the two graphs, and in that case we'd be creating two separate paths from one mcb to another if the other edge is on the same vertex, and we could decompose this into 3 mcb's where all the vertices are even. So basically at any time we want to connect or just expand this graph we need to add an even number of edges which ensures that both the mcb's and the graph are even.
 

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,196
4,540
If the graph G has all even vertices and we want to then show its maximal biconnected components have all of their vertex as even degrees, then I guess that since you have an even graph then every vertex must have an edge going in and going out of it which means that either G would be a collection of cycles or a collection of subgraphs that decompose to cycles, or just 1 vertex with no edges, which I think still counts as an mbc, and all cycles are also biconnected bcause there exists in them no articulation vertex. So I think that counts for one direction.
Sorry, I just don't see how that leads to the conclusion that each mbc has all vertices even degree.
Try this: suppose you have some decomposition of G into cycles; consider the cycles containing a particular vertex; what can you say about the relationship between one of those cycles and the collection of mbcs to which the vertex belongs?
we could add an edge to connect them, but this would violate both the graph being even and the mcb of that one connecting edge being even. So we'd need to add at least one more edge
As I posted, this is not how induction works. It is no use starting with some graph and adding bits. That doesn't necessarily result in constructing every graph. You have to start with the assumption that all graphs smaller than some size have the property, and that some graph just a bit larger does not, then arrive at a contradiction.
 
Sorry, I just don't see how that leads to the conclusion that each mbc has all vertices even degree.
Try this: suppose you have some decomposition of G into cycles; consider the cycles containing a particular vertex; what can you say about the relationship between one of those cycles and the collection of mbcs to which the vertex belongs?
If we combine the cycles that all share a given vertex together, then they should form a mbc?
As I posted, this is not how induction works. It is no use starting with some graph and adding bits. That doesn't necessarily result in constructing every graph. You have to start with the assumption that all graphs smaller than some size have the property, and that some graph just a bit larger does not, then arrive at a contradiction
If I assume that all graphs smaller than some size have the property, is it the same as assuming that for k vertices the graph G has all even degrees and also in all its maximal biconnected components. In that case, to show that some graph just a bit larger does not, do we just add one edge to the graph and show that it creates an odd vertex? That sounds similar to what I did before so I'm not sure what I'm doing wrong.
 
Last edited:

haruspex

Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
31,196
4,540
If we combine the cycles that all share a given vertex together, then they should form a mbc?
No. Consider a graph on five vertices consisting of two triangles sharing a vertex.
do we just add one edge to the graph and show that it creates an odd vertex?
That's wrong in several ways.
First, its the opposite of what you would be wanting to show. You want to show that if the smaller graph has the property then so does the larger - not that the larger does not have the property.
Secondly, it is only graphs of even degree that we wish to show have all mbcs of even degree. To show this is true for a larger graph then you need that larger graph also to be of even degree and show that its mbcs are of even degree. If you add one edge it won't be of even degree, so is irrelevant.
Thirdly, if you try to fix that by adding more edges, how do you know whether you have added them in a totally general manner? Maybe your prescription for adding them misses out some larger graphs.

Let me try again to explain how induction usually works.
1. Pick some size parameter, such as number of vertices or edges or cycles or mbcs or whatever.
2. Show that the proposition is true for all graphs with a given small value of the parameter.
3. Assume it is true for all graphs up to some unknown parameter value N.
4. Deduce that it is also true for all graphs of parameter N+1.
Step 4 is often achieved through reductio ad absurdum: you suppose there exists a graph G of size N+1 which does not have the property then construct from it a smaller graph which would also not have the property. Since that contradicts your assumption in 3, G cannot exist.

In the present case, number of edges isn't going to work as the parameter. If you remove one edge from a graph of even degree it will no longer have even degree, so cannot produce a contradiction to your assumption.
 
Last edited:

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