1: Suppose G = (V, E) is a simple graph (no self-loops or multiple edges). The degree sequence of G is 1, 3, 3, 4, 5. What is the number of edges in G? Problem 2: Suppose T is a tree on 6 vertices and the longest path in T is of length 5 (the length of a path is the number of edges in it). What is the degree sequence of T ? Problem 3: Is the graph K3,4 planar? If yes, give a planar drawing by hand. If not, give a proof of this. Problem 4: Is it possible to have a graph on 6 vertices with the degree sequence 1, 1, 2, 4, 2, 1? Problem 5: Give an example of two non-isomorphic graph on 6 vertices that have the same degree sequence 2, 2, 2, 2, 3, 3. [Hint: Think of a \"cycle with a chord\" for both graphs.] Problem 6: Give a planar drawing of the following graph: b d Problem 7: Are the following graphs isomorphic? If so, give an isomorphism between the two. 6 b 5 d 4 f 3 1 Problem 8: 2 Find a MST of the following graph by using Prim's algorithm - use the starting vertex as a. b 5 2 3 6 6 5 8 3 1 7 d b 4 3 f 4 1 4 i g 4 h 2 Problem 9: Does the greedy coloring algorithm always use (G) + 1 colors on a graph G? If yes, give a proof of this fact. If no, give an example graph G (say with 4 vertices) where this does not happen [Recall that you need to give an ordering on the vertices as well for which the desired fact happens]. Problem 10: Consider the simple graph G = P4 shown below: 1 2 3 4 Answer the following questions for this graph. 1. What is the chromatic number (G)? 2. Find an ordering of the vertices of this graph such that when the greedy coloring algorithm is applied, it does not produce an optimal coloring, i.e., it used more than (G) colors. 3. Find an ordering of the vertices where the greedy algorithm does produce an optimal coloring, i.e., a coloring with (G) colors. Problem 11: A binary tree has the structure shown below and has labels a-g assigned to its nodes. A preorder traversal that prints out the labels at each node during its visit, is b c d e a g f . Label the vertices of the tree below with the appropriate labels. Problem 12: Repeat the above problem with the postorder traversal sequence as a c d f g e b. Problem 13: In a party with n people, every person knows at most 3 other people. Show that there is a group of n/4 people who do not know each other, i.e., none of them know anyone else in the group. Problem 14: Construct a FSM which will accept all binary strings that contain 010. Problem 15: Construct a spanning tree of the following graph: a g 2 d b c f e Problem 16: Output the vertices (as a sequence of the labels assigned to them) in a DFS and a BFS traversal of the following graph. Whenever an ordering of neighbors of a vertex is desired do it lexicographically, i.e., a vertex labeled 'a' will come before a vertex labeled 'b' etc. g c f d a b 3