Given a graph G = (V, E), an edge e E is said to be a bridge if the graph G_0 =

Question

Given a graph G = (V, E), an edge e E is said to be a bridge if the graph G_0 = (V, E {e}) has more connected components than G. Prove that if all vertex degrees in a graph G are even then G has no bridge Prove that given a connected graph G = (V, E), the degrees of all vertices of G are even if and only if there is a set of edge-disjoint cycles in G that cover the edges of G. (That is, the edge set of G is the disjoint union of the edge sets of these cycles.) Prove that if a graph has at most m vertices of degree at most n and all other vertices have degree at most k, with k

Explanation / Answer

1 Solution:

We may assume that G is connected, for otherwise the lemma could be applied to each component separately. For contradiction, suppose that an edge (v1,v2)=e is a bridge of G. The graph G0 = (V,E{e}) has exactly 2 components. Let G1 be the component containing v1. All vertices of G1 have an even degree except for v1 whose degree in G1 is odd. But this is impossible by the handshake lemma.

2 Solution:

This can be proved by strong induction on the number of vertices. For induction basis, consider a graph with a single vertex and propostion holds trivially.

Assume that this holds for all graphs with upto n vertices for n>= 2 .

Now consider a graph G with n+1 vertices. Since each vertex in G is even and of degree at least 2, so G is not a tree. Thus, there is at least one G by deleting all the edges belonging to C.

Since every vertex in a cycle is of degree 2 and every vertex in G' is also even, by induction hypothesis G' has a set of edges that is the disjoint union of edges sets of cycles. Thus, the set of edges of G will be the disjoint union of edge sets of G'' and the deleted cycle.

Conversely, consider a graph with a single vertex (set of edges is empty). Obviously the vertex has an even degree. Assume that this holds for all graphs with upto n vertices for n>=2. Now consider a connected graph G with n+1 vertices such that the set of edges in G is the disjoint union of m cycles. Consider any one of these cycels say C. Since G is connected, there is a vertex in common between C and the rest of the graph G'', obtained by omitting the edges in cycle C from the set of edges of G. Since every vertex in a cycle has degree 2 and by our induction hypothesis all vertices in G1 have even degrees, all vertices in G will have even degrees. This concludes the proof

3 Solution:

First consider the reduced problem of coloring the graph minus the m vertices of degree atmost m and all edges involving those vertices. Since all remaining vertices have degree k or less, k+1 colors are enough for the reduced graph. Then if we restore the original graph and assign one color not used to each of the m vertices, the resulting graph will be colored using m+k+1 colors.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.