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 sum V, then every undiscovered vertex v such that w has a path to v must be discovered before DFS returns from u. 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| less then are equal to |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