Each Question is worth 2 marks. 1. Derive the generating function A for a series an if an is defined recursively as an = an-1-2an-2 and a0 = -1, a1 = 2. Show that if we use the reverse of the...

Each Question is worth 2 marks. 1. Derive the generating function A for a series an if an is defined recursively as an = an-1-2an-2 and a0 = -1, a1 = 2. Show that if we use the reverse of the recurrence relation, i.e. A-an-1A+2an-2A2 , terms will cancel and this equals 1. By finding the solution to the recurrence relation, derive a closed formula for the sequence. 2. Prove that any graph has at least two vertices with the same degree. A complete bipartite graph on ( m , n ) vertices, is a simple graph whose vertices can be divided into two distinct, non-overlapping sets (that is, suppose V has m vertices and W has n vertices) in such a way that there is exactly one edge from each vertex of V to each vertex of W , there is no edge from any one vertex of V to any other vertex of V , and there is no edge from any one vertex of W to any other vertex of W. Use ways to select the edges to show that this graph has m.n edges Use combinations to show that the number of edges on a complete graph is n(n-1)/2 3. If G is a colored graph in which each vertex is assigned a color. The chromatic number of a graph G, denoted ?(G), is the least number of distinct colors with which G can be properly colored. That is, it is a coloring of the vertices of G with the property that no two adjacent vertices have the same color. In a graph, pairwise non-adjacent vertices or edges are called independent. The maximum number of independent vertices of G if defined as a(G). Prove that in any graph G with n vertices, the number n is less than the multiple of these two values of the Graph. 4. A combinatorial proof of an identity is a proof that uses counting arguments to prove that both sides of the identity count the same objects but 1 in different ways or a proof that is based on showing that there is a bijection between the sets of objects counted by the two sides of the identity. These two types of proofs are called double counting proofs and bijective proofs , respectively. Use such a method to prove that 2n divides n! whenever n is an even positive integer. Consider the number of permutations of 2n objects where there are two indistinguishable objects of n different types 5. Fleury’s algorithm is an optimisation solution for finding a Euler Circuit of Euler Path in a graph, if they exist. Describe how this algorithm will always find a path or circuit if it exists. Describe how you calculate if the graph is connected at each edge removal. Fleury’s Algorithm: The algorithm starts at a vertex of v odd degree, or, if the graph has none, it starts with an arbitrarily chosen vertex. At each step it chooses the next edge in the path to be one whose deletion would not disconnect the graph, unless there is no such edge, in which case it picks the remaining edge (a bridge) left at the current vertex. It then moves to the other endpoint of that edge and adds the edge to the path or circuit. At the end of the algorithm there are no edges left ( or all your bridges are burnt).