Could someone help me with the problems below Let d be the maximum degree of the
ID: 3827566 • Letter: C
Question
Could someone help me with the problems below Let d be the maximum degree of the vertices in a graph G. Prove that we can color G with d + 1 colors. Consider this statement: In any directed graph G = (V, E), when DFS visits a vertex u element V, then every undiscovered vertex v such that u has a path to v must be discovered before DFS returns from us. Is this statement true or false? If true, give a proof if false, give a counterexample. Consider this statement: In any undirected graph G = (V, E), there must be an even number of vertices whose degree is odd. Is this statement true or false? If true, give a proof; if false, give a counterexample. Consider the problem of determining whether an undirected graph G = (V, E) contains a triangle (cycle of length three). (a) Give an O(|V|^3) to find a triangle if one exists. (b) Improve your algorithm to run in time O(|V| middot |E|). You may assume |V| lessthanorequalto |E|. You are given a weighted graph and its minimum spanning tree. There are n vertices and m edges in the graph. (a) Design a polynomial-time algorithm that finds the smallest change in the weight of a non-MST edge that would cause a change in the MST. (b) Analyze the runtime of your algorithm in terms of n and m.Explanation / Answer
Hi Student,
I am answering only question number 1 because it is against chegg policy to anwer more than one question in a single ask. Hope you understand.
Some Background:
The relationship between the maximum degree 'd' of a graph and its chromatic number k is k=d+1. This is also called Brooks Theorem. Chromatic number of a graph is the least number of colors needed to color the vertices of graph so that no two adjacent vertices share the same color.
Now we prove the statement using induction method:
We are using the induction based on the number of vertices in the graph. Let us assume that vertices of graph G is denoted by v. Let P(v) be the proposition that an v-vertex graph with maximum degree at most d is (d + 1)-colorable.
Initial case: V=1 ( number of vertices is 1)
* A 1-vertex graph has maximum degree 0 and is 1-colorable. so P (1) is correct.
Induction steps:
Step1 :
let us assume that P(v) is true, and let G be an (v + 1) vertex graph with maximum degree at most d.
step2:
Remove a vertex k (and all edges incident to it), leaving an n-vertex subgraph, M. The maximum degree of M is at most d, and so M is (d + 1)-colorable by our assumption P (v).
step3:
Now add vertex k back. We can assign k a color (from the set of d + 1 colors) that is different from all its adjacent vertices, since there are atmost d vertices adjacent to k and hence atleast one of the d + 1 colors is still present.
Step4:
Hence, G is (d + 1) colorable.
This step completes the inductive step. Hence proved.