exercises 10. (a) Supposeadictionaryinacomputerhasa\"start\"fromwhichonecanbranchtoany of the 26 letters: at any letter one can go to the preceding and succeedingletters. Model this data structure with a graph. (b) Suppose additionally that one can return to \"start\" from letters c or k or t .Now what is the longest directed path between any two letters? 16. (a) For the following graph, nd all sets of two vertices whose removal discon-nects the graph of remaining vertices. (b) Find all sets of two edges whose removal would disconnect the graph. Example 4: Street Surveillance Now suppose the graph in Figure 1.4 represents a section of a city's street map. Wewant to position police ofcers at corners (vertices) so that they can keep every block (edge) under surveillancethat is, every edge should have police ofcers at (at least)one of its end vertices. What is the smallest number of police ofcers that can do this job? 20. Repeat Example 4 for the edge cover and minimal corner surveillance when thenetworkisformedbyaregulararrayofnorth-southandeast-weststreetsofsize: (a) 3 streets by 3 streets (b) 4 streets by 4 streets (c) 5 streets by 5 streets 22. Solve the committee scheduling problem for the committee overlap graph inFigure 1.4. That is, what is the minimum number of independent sets needed to cover all vertices? 24. What is the largest independent set in a circuit of length 7? Of length n ? 26. Find a vertex basis in the following directed graphs: (b) Figure 1.3 (c) Figure 1.4 with edges directed by alphabetical order [e.g., edge ( a , e ) is directed from a to e ] 27. Show that the vertex basis in a directed graph is unique if there is no sequence of directed edges that forms a circuit in the graph. 28. A game for two players starts with an empty pile. Players take turns putting one,two, or three pennies in the pile. The winner is the player who brings the valueof the pile up to 16c / . (a) Make a directed graph modeling this game. (b) Show that the second player has a winning strategy by nding a set of four\"good\" pile values, including 16c / , such that the second player can alwaysmove to one of the \"good\" piles (when the second player moves to one of the good piles, the next move of the rst player must be to a non-good pile,and from this position the second player has a move to a good pile, etc.). 1.2 exercises 6. Which of the following pairs of graphs are isomorphic? Explain carefully. 8. Which pairs of graphs in this set are isomorphic? 11. Show that all 5-vertex graphs with each vertex of degree 2 are isomorphic. 12. Are there any 6-vertex graphs with three edges incident to each vertex that are not isomorphic to one of the following graphs ? 14. Build 6-vertex graphs with the following degrees of vertices, if possible. If notpossible, explain why not. (a) Three vertices of degree 3 and three vertices of degree 1 (b) Vertices of degrees 1, 2, 2, 3, 4, 5 (c) Vertices of degrees 2, 2, 4, 4, 4, 4 . \f