Question regarding degrees of a graph and its biconnected components

[Superyoshiom]

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]

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.

 

[Superyoshiom]

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:

 

[haruspex]

I admit it might have sounded a bit ambiguous, I've attached the problem here:
View attachment 244791

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:

we can't just connect the biconnected components together with one edge, because then the degree of the vertices would become odd.

 

[Superyoshiom]

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]

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.

 

[Superyoshiom]

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]

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

 

[Superyoshiom]

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]

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.

 

[Superyoshiom]

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]

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.

 

[Superyoshiom]

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:

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]

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.

 

[haruspex]

that v and u refer to the same vertices?

Yes and no. Each is independently the subject of a "for all".

 

[Superyoshiom]

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]

is it true that two vertices and an edge between them is biconnected, since removing one vertex removes the edge altogether.

Yes.

I just need to show that there are no odd degrees in the rest of the graph.

That does not sound right. Please explain your logic in more detail.

 

[Superyoshiom]

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]

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.

 

[Superyoshiom]

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]

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?

 

[Superyoshiom]

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]

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?

 

[Superyoshiom]

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]

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.

 

[Superyoshiom]

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]

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 anyone vertex of G.
Can you show there must still be a path from w to w'

 

[Superyoshiom]

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 anyone 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'

 

[haruspex]

since we have at least two vertices that can reach u

vertices? You mean paths?

removing only one vertex can remove at most one path to either u and v

Or remove u or v.

 

[Superyoshiom]

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]

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.

 

[Superyoshiom]

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]

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.

 

[Superyoshiom]

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.

 

[haruspex]

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.