Question 4: Counting Problems of the questions below, your answer must consist of a formula in vertices n, along with a brief but concise justification of its correctness. Answers without sufficient justification will receive no marks (a) We know that the maximum number of possible edges in a graph on n vertices is (2)--(n.1) Derive a formula which counts the number of possible graphs on n vertices (with no restrictions whatsoever on the structure of the graph, besides that it has n vertices and is an undirected simple graph). (b) Suppose G is a graph on n vertices with exactly three connected components. Derive a formula for the maximum number of edges in G (c) Suppose G is a directed acyclic graph with exactly k minimum vertices. Derive a formula (in terms of n and k) for the minimum number of directed edges in G