Please answer questions labeled (3) and the bonus part at the bottom. Please verify answers to (1) and (2).. Provide clear steps for my understanding. Thanks!

Bonus -

Answers to verify ----------------------------------------------------------------------------------------------------------------

A graph G=(V,E) is complete if for all s,tV, there is an edge (s,t)E. Answer these questions: (1) How many edges does a complete graph G having n nodes have? Prove this inductively. State your inductive hypothesis clearly. (Five points) (2) How many iterations of DFS does it take to traverse a complete graph having n nodes? Explain (but don't prove) why this is. (One point) (3) How many iterations of BFS does it take to traverse a complete graph having n nodes? Explain (but don't prove) why this is. (One point) Students taking the course for graduate credit, and undergraduates for a little extra credit, prove the following. Let G be a graph having n nodes, where n is an even number. If every node of G has degree at least n/2, then G is connected. (1) A complete graph with n nodes has (n(n1))/2 edges. Proof by induction: Base case: n=2, a complete graph with 2 nodes has only 1 edge, and (2(21))/2=1. Inductive Hypothesis: Assume that a complete graph with k nodes has (k(k1))/2 edges, where k is some positive integer. Inductive Step: Let's consider a complete graph with k+1 nodes. To count the number of edges, we can note that each of the k+1 nodes is connected to the other k nodes in the graph. Therefore, the total number of edges in the graph is the sum of the edges connecting the k+1 node to the other k nodes plus the edges in the complete graph with k nodes. Since the complete graph with k nodes has (k(k 1))/ 2 edges (by our inductive hypothesis), the total number of edges in the complete graph with k+1 nodes is: (k(k1))/2+k=k(k+1)/2 (2) It takes only one iteration of DFS to traverse a complete graph with n nodes, as every node is connected to every other node. For BFS, it would take n1 iterations to traverse a complete graph with n nodes, as the traversal would start from one node and visit all the other nodes one by one. Claim: If every node of a graph G with n nodes has degree at least n/2, then G is connected. Proof: We prove the claim by contradiction. Suppose G is not connected. Then, G can be partitioned into two non-empty sets of vertices, A and B, such that no edge exists between A and B. Without loss of generality, assume that A has k nodes and B has nk nodes, where 1