Show that every tournament has a Hamilton path.

Problem 1E How many edges does a 50-regular graph with 100 vertices have?

Problem 2E How many nonisomorphic subgraphs does K3 have?

In Exercises 3–5 determine whether two given graphs are isomorphic.

In Exercises 3–5 determine whether two given graphs are isomorphic.

Problem 5E In Exercises 3-5 determine whether two given graphs are isomorphic. The complete m-partite graph kn1,n2,......nm has vertices partitioned into m subsets n1,n2,.....nm elements each, and vertices are adjacent if and only if they are in different subsets in the partition.

Problem 6E Draw these graphs. a) K1,2,3 ________________ b) K2,2,2 ________________ c) K1,2,2,3.

Problem 7E How many vertices and how many edges does the complete m-partite graph K n1,n2,......nmhave?

Problem 8E Prove or disprove that there are always two vertices of the same degree in a finite multigraph having at least two vertices.

Problem 9E Let G = (V,E) be an undirected graph and let A ? V and B ? V. Show that a) N(A U B) = N(A) U N(B). ________________ b) N(A ? B) ? N(A) ? N(B), and give an example where N(A ? B) ? N(A) ?N(B).

Problem 10E Let G=(V.E)be an undirected graph.Show that a) |N(v)|?deg(v)for all v?V. b) |N(v)| = deg v for all v ? V if and only if G is a simple graph. Suppose that S1, S2, .... Sn is a collection of subsets of a set S where n is a positive integer. A system of distinct representatives (SDR) for this family is an ordered n-tuple (a1,a2,... ,an) with the property that ai? Si for i = 1,2,....n and ai? aj­ for all i ? j.

Problem 12E Use Hall’s marriage theorem to show that a collection of finite subsets S1, S2,...Sn of a set S has a SDR(a1, a2, .... an ) if and only if for all sub-sets I of {1,2,....n}.

Problem 11E Find a SDR for the sets S1 = {a, c, m, e}. S2 = {m.a.c.e), S3 = {a, p, e, x}, S4 = {x, e, n, a), S5 = {n, a. m, e}, and S6, = {e, x, a, m}.

Problem 13E a) Use Exercise 12 to show that the collection of sets S1 = {a. b. c}, S2 = {b, c. d}, S3 = {a, b. d}. S4 = {b,c,d} has a SDR without finding one explicitly. ________________ b) Find a SDR for the family of four sets in part (a).

Problem 15E We say that three vertices u, v. and w of a simple graph G form a triangle if there are edges connecting all three pairs of these vertices. Find a formula for C(G) in terms of the number of triangles in G and the number of paths of length two in the graph. [Hint: Count each triangle in the graph once for each order of three vertices that form it.]

Problem 14E Use Exercise 12 to show that collection of sets S1 = {a. b. c}, S2 = {a, c}, S3 = {c. d, e}, S4 = {b, c}, S5 = {d, e. f}, S6, = {a, c,e} and S7 = {a, b} does not have a SDR. The clustering coefficient C(G) of a simple graph G is the probability that if u and v are neighbors and v and w are neighbors, then u and w are neighbors, where u, v, and w are distinct vertices of G.

Problem 16E Find the clustering coefficient of each of the graphs in Exercise 20 of Section 10.2

Problem 17E Explain what the clustering coefficient measures in each of these graphs. a) the Hollywood graph ________________ b) the graph of Facebook friends ________________ c) the academic collaboration graph for researchers in graph theory ________________ d) the protein interaction graph for a human cell ________________ e) the graph representing the routers and communications links that make up the worldwide Internet

Problem 18E For each of the graphs in Exercise 17, explain whether you would expect its clustering coefficient to be closer to 0.01 or to 0.10 and why you expect this.

A dominating set of vertices in a simple graph is a set of vertices such that every other vertex is adjacent to at least one vertex of this set. A dominating set with the least number of vertices is called a minimum dominating set. In Exercises 22–24 find a minimum dominating set for the given graph.

Problem 21E A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. In Exercises 19-21 find all cliques in the graph shown.

A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. In Exercises 19–21 find all cliques in the graph shown.

Problem 19E A clique in a simple undirected graph is a complete subgraph that is not contained in any larger complete subgraph. In Exercises 19-21 find all cliques in the graph shown.

Problem 23E A dominating set of vertices in a simple graph is a set of vertices such that every other vertex is adjacent to at least one vertex of this set. A dominating set with the least number of vertices is called a minimum dominating set. In Exercises 22-24 find a minimum dominating set for the given graph.

A simple graph can be used to determine the minimum number of queens on a chessboard that control the entire chessboard. An \(n \times n\) chessboard has \(n^{2}\) squares in an \(n \times n\) configuration. A queen in a given position controls all squares in the same row, the same column, and on the two diagonals containing this square, as illustrated. The appropriate simple graph has \(n^{2}\) vertices, one for each square, and two vertices are adjacent if a queen in the square represented by one of the vertices controls the square represented by the other vertex. 25. Construct the simple graph representing the \(n \times n\) chessboard with edges representing the control of squares by queens for a) \(n=3\). b) \(n=4\). Equation Transcription: Text Transcription: n x n n^2 n=3 n=4

Problem 24E A dominating set of vertices in a simple graph is a set of vertices such that every other vertex is adjacent to at least one vertex of this set. A dominating set with the least number of vertices is called a minimum dominating set. In Exercises 22-24 find a minimum dominating set for the given graph.

Problem 26E A simple graph can be used to determine the minimum number of queens on a chessboard that control the entire chessboard. An n ×n chessboard has n2 squares in an n×n configuration. A queen in a given position controls all squares in the same row, the same column, and on the two diagonals containing this square, as illustrated. The appropriate simple graph has n2 vertices, one for each square, and two vertices are adjacent if a queen in the square represented by one of the vertices controls the square represented by the other vertex. Explain how the concept of a minimum dominating set applies to the problem of determining the minimum number of queens controlling an n × n chessboard.

Problem 28E Suppose that G 1 and H1are isomorphic and that G 2and H2 are isomorphic. Prove or disprove that G1 È G 2 and H1 È H2 are isomorphic.

A simple graph can be used to determine the minimum number of queens on a chessboard that control the entire chessboard. An \(n \times n\) chessboard has \(n^{2}\) squares in an \(n \times n\) configuration. A queen in a given position controls all squares in the same row, the same column, and on the two diagonals containing this square, as illustrated. The appropriate simple graph has \(n^{2}\) vertices, one for each square, and two vertices are adjacent if a queen in the square represented by one of the vertices controls the square represented by the other vertex. Find the minimum number of queens controlling an \(n \times n\) chessboard for a) \(n=3\). b) \(n=4\). c) \(n=5\). Equation Transcription: Text Transcription: n x n n^2 n=3 n=4 n=5

Problem 29E Show that each of these properties is an invariant that isomorphic simple graphs either both have or both do not have. a) connectedness ________________ b) the existence of a Hamilton circuit ________________ c) the existence of an Euler circuit ________________ d) having crossing number C ________________ e) having n isolated vertices ________________ f) being bipartite

Problem 31E How many nonisomorphic connected bipartite simple graphs are there with four vertices?

Problem 30E How can the adjacency matrix of be found from the adjacency matrix of G. where G is a simple graph?

Problem 32E How many nonisomorphic simple connected graphs with five vertices are there a) with no vertex of degree more than two? ________________ b) with chromatic number equal to four? ________________ c) that are nonplanar? A directed graph is self-converse if it is isomorphic to its converse.

Determine whether the following graphs are self-converse.

Problem 34E Show that if the directed graph G is self-converse and H is a directed graph isomorphic to G, then H is also self-converse.

An orientation of an undirected simple graph is an assignment of directions to its edges such that the resulting directed graph is strongly connected. When an orientation of an undirected graph exists, this graph is called orientable. In Exercises 35–37 determine whether the given simple graph is orientable.

Problem 35E An orientation of an undirected simple graph is an assignment of directions to its edges such that the resulting directed graph is strongly connected. When an orientation of an undirected graph exists, this graph is called orientable. In Exercises 35-37 determine whether the given simple graph is orientable.

Problem 36E An orientation of an undirected simple graph is an assignment of directions to its edges such that the resulting directed graph is strongly connected. When an orientation of an undirected graph exists, this graph is called orientable. In Exercises 35-37 determine whether the given simple graph is orientable.

Problem 38E Because traffic is growing heavy in the central part of a city, traffic engineers are planning to change all the streets, which are currently two-way, into one-way streets. Explain how to model this problem.

Problem 39E Show that a graph is not orientable if it has a cut edge. A tournament is a simple directed graph such that if u and v are distinct vertices in the graph, exactly one of (u, v) and (v, u) is an edge of the graph.

Problem 40E How many different tournaments are there with n vertices?

Problem 41E What is the sum of the in-degree and out-degree of a vertex in a tournament?

Problem 42E Show that every tournament has a Hamilton path.

Problem 44E Suppose that a connected graph G has n vertices and vertex connectivity k(G) = k. Show that G must have at least [kn/2] edges. A connected graph G = (V,E) with n vertices and m edges is said to have optimal connectivity if k(G) = ?(G) = minv?V deg v = 2m/n.

Problem 47E Find the two nonisomorphic simple graphs with six vertices and nine edges that have optimal connectivity.

Problem 46E Show these graphs have optimal connectivity. a) Cn for n?3 ________________ b) kn for n?3 ________________ c) kr,r for n?2

Problem 45E Show that a connected graph with optimal connectivity must be regular.

Problem 43E Given two chickens in a flock, one of them is dominant. This defines the pecking order of the flock. How can a tournament be used to model pecking order?

Problem 48E Suppose that G is a connected multigraph with 2k vertices of odd degree. Show that there exist k subgraphs that have G as their union, where each of these subgraphs has an Euler path and where no two of these subgraphs have an edge in common. [Hint: Add k edges to the graph connecting pairs of vertices of odd degree and use an Euler circuit in this larger graph.]

Problem 49E In Exercises 49 and 50 we consider a puzzle posed by Petkovic in [Pe09] (based on a problem in [AvCh80]). Suppose that King Arthur has gathered his 2n knights of the Round Table for an important council. Every two knights are either friends or enemies, and each knight has no more than n — 1 enemies among the other 2n — 1 knights. The puzzle asks whether King Arthur can seat his knights around the Round Table so that each knight has two friends for his neighbors. a) Show that the puzzle can be reduced to determining whether there is a Hamilton circuit in the graph in which each knight is represented by a vertex and two knights are connected in the graph if they are friends. ________________ b) Answer the question posed in the puzzle. [Hint: Use Dirac’s theorem.]

Problem 50E In Exercises 49 and 50 we consider a puzzle posed by Petkovic in [Pe09] (based on a problem in [AvCh80]). Suppose that King Arthur has gathered his 2n knights of the Round Table for an important council. Every two knights are either friends or enemies, and each knight has no more than n — 1 enemies among the other 2n — 1 knights. The puzzle asks whether King Arthur can seat his knights around the Round Table so that each knight has two friends for his neighbors.0. Suppose that are eight knights Alynore, Bedivere, Degore. Gareth. Kay. Lancelot, Perceval, and Tristan. Their lists of enemies are A (D, G, P), B (K, P, T), D (A. G, L), G (A, D, T), K (B, L, P), L (D, K, T), P (A, B, K), T (B, G, L), where we have represented each knight by the first letter of his name and shown the list of enemies of that knight following this first letter. Draw the graph representing these eight knight and their friends and find a seating arrangement where each knight sits next to two friends.

Problem 51E Let G be a simple graph with n vertices. The bandwidth of G, denoted by B(G), is the minimum, overall permutations a1, a2,... ,an of the vertices of G, of max {|i-j||ai,and aj are adjacent}. That is, the bandwidth is the minimum over all listings of the vertices of the maximum difference in the indices assigned to adjacent vertices. Find the bandwidths of these graphs. a) K5 ________________ b) K 1,3 ________________ c) K2,3 ________________ d) K3,3 ________________ e) Q3 ________________ f) C5

The distance between two distinct vertices \(v_{1}\) and \(v_{2}\) of a connected simple graph is the length (number of edges) of the shortest path between \(v_{1}\) and \(v_{2}\). The radius of a graph is the minimum over all vertices \(v\) of the maximum distance from \(v\) to another vertex. The diameter of a graph is the maximum distance between two distinct vertices. Find the radius and diameter of a) \(K_{6}\). b) \(K_{4,5}\). c) \(Q_{3}\). d) \(C_{6}\). Equation Transcription: Text Transcription: v_1 v_2 v K_6 K_4,5 Q_3 C_6

Problem 53E a) Show that if the diameter of the simple graph G is at least four, then the diameter of its complement is no more than two. ________________ b) Show that if the diameter of the simple graph G is at least three, then the diameter of its complement is no more than three.

Problem 54E Suppose that a multigraph has 2m vertices of odd degree. Show that any circuit that contains every edge of the graph must contain at least m edges more than once.

Problem 56E Devise an algorithm for finding the second shortest path between two vertices in a simple connected weighted graph.

Problem 57E Find the shortest path between the vertices a and z that passes through the vertex f in the weighted graph in Exercise 3 in Section 10.6.

Problem 58E Devise an algorithm for finding the shortest path between two vertices in a simple connected weighted graph that passes through a specified third vertex.

Problem 60E A set of vertices in a graph is called independent if no two vertices in the set are adjacent. The independence number of a graph is the maximum number of vertices in an independent set of vertices for the graph. What is the independence number of a) Kn? ________________ b) Cn? ________________ c) Qn? ________________ d) Km,n?

Problem 59E Show that if G is a simple graph with at least 11 vertices, then either G or , the complement of G, is nonplanar.

Problem 55E Find the second shortest path between the vertices a and z in Figure 3 of Section 10.6.

Problem 62E Show that the chromatic number of a graph is less than or equal to n -i + 1, where n is the number of vertices in the graph and i is the independence number of this graph.

Problem 61E Show that the number of vertices in a simple graph is less than or equal to the product of the independence number and the chromatic number of the graph.

Problem 63E Suppose that to generate a random simple graph with n vertices we first choose a real number p with 0 ? p ? 1. For each of the C(n, 2) pairs of distinct vertices we generate a random number x between 0 and 1. If 0 ? x ? p, we connect these two vertices with an edge; otherwise these vertices are not connected. a) What is the probability that a graph with m edges where 0 ? m ? C(n,2) is generated? ________________ b) What is the expected number of edges in a randomly generated graph with n vertices if each edge is included with probability p? ________________ c) Show that if p = 1 /2 then every simple graph with n vertices is equally likely to be generated. A property retained whenever additional edges are added to a simple graph (without adding vertices) is called monotone increasing, and a property that is retained whenever edges are removed from a simple graph (without removing vertices) is called monotone decreasing.

Problem 64E For each of these properties, determine whether it is monotone increasing and determine whether it is monotone decreasing. a) The graph G is connected. ________________ b) The graph G is not connected. ________________ c) The graph G has an Euler circuit. ________________ d) The graph G has a Hamilton circuit. ________________ e) The graph G is planar. ________________ f) The graph G has chromatic number four. ________________ g) The graph G has radius three. ________________ h) The graph G has diameter three.

Problem 66E Suppose that P is a monotone increasing property of simple graphs. Show that the probability a random graph with n vertices has property P is a monotonic nondecreasing function of p, the probability an edge is chosen to be in the graph.

Problem 65E Show that the graph property P is monotone increasing if and only if the graph property Q is monotone decreasing where Q is the property of not having property P.