1.Prove that an undirected graph must have an even number of nodes (vertices) of odd degree. Restrict your answer to the rest of this page (but you shouldnt need that much space). You may wish to phrase your proof in terms of the number of edges e and/or the number of nodes v in the graph

2.When searching a graph, it is useful to be able to detect when that graph has a cycle. Consider the case of an undirected graph where you only want to know whether a given edge is part of any cycle. Give an algorithm that can determine this below. Your algorithm must run in linear (or better [e.g., logarithmic or constant] time in both the number of vertices v in the graph and the number of edges e in the graph. Again, describe and analyze your algorithm on this page, or at worst this page and one other (again, its short if you understand search).