Show that a graph is bipartite if, and only if, it does

Problem 50E Show that a graph is bipartite if, and only if, it does not have a circuit with an odd number of edges. (See exercise for the definition of bipartite graph.) bipartite graph A bipartite graph G is a simple graph whose vertex set can be partitioned into two disjoint nonempty subsets V1 and V2 such that vertices in V1 may be connected to vertices in V2, but no vertices in V1 are connected to other vertices in V1 and no vertices in V2 are connected to other vertices in V2.For example, the graph G illustrated in (i) can be redrawn as shown in (ii). From the drawing in (ii), you can see that G is bipartite with mutually disjoint vertex sets V1 = {v1, v3, v5} and V2 = {v2, v4, v6}. (i) ________________ (ii) Find which of the following graphs are bipartite. Redraw the bipartite graphs so that their bipartite nature is evident a. ________________ b. ________________ c. ________________ d. ________________ e. ________________ f.

Problem 1E In the graph below, determine whether the following walks are trails, paths, closed walks, circuits, simple circuits, or just walks. a.v0e1v1e10v5e9v2e2v1 ________________ b. v4e7v2e9v5e10v1e3v2e9v5 ________________ c. v2 ________________ d. v5v2v3v4v4v5 ________________ e. v2v3v4v5v2v4v3v2 ________________ f. e5e8e10e3

Problem 4E Consider the following graph.

Problem 2E In the graph below, determine whether the following walks are trails, paths, closed walks, circuits, simple circuits, or just walks. a. v1e2v2e3v3e4v4e5v2e2v1e1v0 ________________ b. v2v3v4v5v2 ________________ c. v4v2v3v4v5v2v4 ________________ d. v2v1v5v2v3v4v2 ________________ e. v0v5v2v3v4v2v1 ________________ f. v5v4v2v1

Problem 3E Problem Let G be the graph and consider the walk v1e1v2e2v1. a. Can this walk be written unambiguously as v1v2v1? Why? ________________ b. Can this walk be written unambiguously as e1e2? Why?

Problem 6E An edge whose removal disconnects the graph of which it is a part is called a bridge. Find all bridges for each of the following graphs. a. ________________ b. ________________ c.

Problem 5E Consider the following graph. a. How many paths are there from a to c? ________________ b. How many trails are there from a to c? ________________ c. How many walks are there from a to c?

Problem 12E Determine which of the graphs in have Euler circuits. If the graph does not have an Euler circuit, explain why not. If it does have an Euler circuit, describe one.

Problem 11E Is it possible for a citizen of Konigsberg to make a tour of the city and cross each bridge exactly twice? (See Figure) Why? Figure The Seven Bridges of Königsberg

Problem 7E Given any positive integer n, (a) find a connected graph with n edges such that removal of just one edge disconnects the graph; (b) find a connected graph with n edges that cannot be disconnected by the removal of any single edge.

Problem 8E Find the number of connected components for each of the following graphs. a. ________________ b. ________________ c. ________________ d.

Problem 9E Each of (a)–(c) describes a graph. In each case answer yes, no, or not necessarily to this question: Does the graph have an Euler circuit? Justify your answers. a. G is a connected graph with five vertices of degrees 2, 2, 3, 3, and 4. ________________ b. G is a connected graph with five vertices of degrees 2, 2, 4, 4, and 6. ________________ c. G is a graph with five vertices of degrees 2, 2, 4, 4, and 6.

Problem 10E The solution for Example shows a graph for which every vertex has even degree but which does not have an Euler circuit. Give another example of a graph satisfying these properties. Example Showing That a Graph Does Not Have an Euler Circuit Show that the graph below does not have an Euler circuit. Solution Vertices v1 and v3 both have degree 3, which is odd. Hence by (the contrapositive form of) Theorem, this graph does not have an Euler circuit. Theorem If a graph has an Euler circuit, then every vertex of the graph has positive even degree. Proof: Suppose G is a graph that has an Euler circuit. [We must show that given any vertex v of G, the degree of v is even.] Let v be any particular but arbitrarily chosen vertex of G. Since the Euler circuit contains every edge of G, it contains all edges incident on v. Now imagine taking a journey that begins in the middle of one of the edges adjacent to the start of the Euler circuit and continues around the Euler circuit to end in the middle of the starting edge. (See Figure. There is such a starting edge because the Euler circuit has at least one edge.) Each time v is entered by traveling along one edge, it is immediately exited by traveling along another edge (since the journey ends in the middle of an edge). Figure Example for the Proof of Theorem In this example, the Euler circuit is v0v1v2v3v4v2v5v0, and v is v2. Each time v2 is entered by one edge, it is exited by another edge. Because the Euler circuit uses every edge of G exactly once, every edge incident on v is traversed exactly once in this process. Hence the edges incident on v occur in entry/exit pairs, and consequently the degree of v must be a positive multiple of 2. But that means that v has positive even degree [as was to be shown].

Problem 14E Determine which of the graphs in have Euler circuits. If the graph does not have an Euler circuit, explain why not. If it does have an Euler circuit, describe one.

Problem 13E Determine which of the graphs in have Euler circuits. If the graph does not have an Euler circuit, explain why not. If it does have an Euler circuit, describe one.

Problem 15E Determine which of the graphs in have Euler circuits. If the graph does not have an Euler circuit, explain why not. If it does have an Euler circuit, describe one.

Problem 17E Determine which of the graphs in have Euler circuits. If the graph does not have an Euler circuit, explain why not. If it does have an Euler circuit, describe one.

Problem 16E Determine which of the graphs in have Euler circuits. If the graph does not have an Euler circuit, explain why not. If it does have an Euler circuit, describe one.

Problem 18E Is it possible to take a walk around the city whose map is shown below, starting and ending at the same point and crossing each bridge exactly once? If so, how can this be done?

Problem 19E For each of the graphs in determine whether there is an Euler trail from u to w. If there is, find such a path.

Problem 21E For each of the graphs in determine whether there is an Euler trail from u to w. If there is, find such a path.

Problem 20E For each of the graphs in determine whether there is an Euler trail from u to w. If there is, find such a path.

Problem 22E The following is a floor plan of a house. Is it possible to enter the house in room A, travel through every interior doorway of the house exactly once, and exit out of room E? If so, how can this be done?

Problem 24E Find Hamiltonian circuits for each of the graphs in

Problem 25E Show that none of the graphs in has a Hamiltonian circuit.

Problem 23E Find Hamiltonian circuits for each of the graphs in

Problem 27E Show that none of the graphs in has a Hamiltonian circuit.

Problem 28E In find Hamiltonian circuits for those graphs that have them. Explain why the other graphs do not.

Problem 29E In find Hamiltonian circuits for those graphs that have them. Explain why the other graphs do not.

Problem 26E Show that none of the graphs in has a Hamiltonian circuit.

Problem 30E In find Hamiltonian circuits for those graphs that have them. Explain why the other graphs do not.

Problem 31E In find Hamiltonian circuits for those graphs that have them. Explain why the other graphs do not.

Problem 33E Give two examples of graphs that have Hamiltonian circuits but not Euler circuits.

Problem 32E Give two examples of graphs that have Euler circuits but not Hamiltonian circuits.

Problem 34E Give two examples of graphs that have circuits that are both Euler circuits and Hamiltonian circuits.

Problem 35E Give two examples of graphs that have Euler circuits and Hamiltonian circuits that are not the same.

Problem 36E A traveler in Europe wants to visit each of the cities shown on the map exactly once, starting and ending in Brussels. The distance (in kilometers) between each pair of cities is given in the table. Find a Hamiltonian circuit that minimizes the total distance traveled. (Use the map to narrow the possible circuits down to just a few. Then use the table to find the total distance for each of those.) Berlin Brussels Düsseldorf Luxembourg Munich Brussels 783 Düsseldorf 564 223 Luxembourg 764 219 224 Munich 585 771 613 517 Paris 1,057 308 497 375 832

Problem 37E a.Prove that if a walk in a graph contains a repeated edge, then the walk contains a repeated vertex. b. Explain how it follows from part (a) that any walk with no repeated vertex has no repeated edge.

Problem 38E Prove Lemma: If G is a connected graph, then any two distinct vertices of G can be connected by a path. Lemma Let G be a graph. a. If G is connected, then any two distinct vertices of G can be connected by a path. ________________ b. If vertices v and w are part of a circuit in G and one edge is removed from the circuit, then there still exists a trail from v to w in G. ________________ c. If G is connected and G contains a circuit, then an edge of the circuit can be removed without disconnecting G.

Problem 39E Prove Lemma: If vertices v and w are part of a circuit in a graph G and one edge is removed from the circuit, then there still exists a trail from v to w in G. Lemma Let G be a graph. a. If G is connected, then any two distinct vertices of G can be connected by a path. ________________ b. If vertices v and w are part of a circuit in G and one edge is removed from the circuit, then there still exists a trail from v to w in G. ________________ c. If G is connected and G contains a circuit, then an edge of the circuit can be removed without disconnecting G.

Problem 40E Draw a picture to illustrate Lemma: If a graph G is connected and G contains a circuit, then an edge of the circuit can be removed without disconnecting G. Lemma Let G be a graph. a. If G is connected, then any two distinct vertices of G can be connected by a path. ________________ b. If vertices v and w are part of a circuit in G and one edge is removed from the circuit, then there still exists a trail from v to w in G. ________________ c. If G is connected and G contains a circuit, then an edge of the circuit can be removed without disconnecting G.

Problem 43E Prove that if there is a circuit in a graph that starts and ends at a vertex v and if w is another vertex in the circuit, then there is a circuit in the graph that starts and ends at w.

Problem 47E For what values of n does the complete graph Kn with n vertices have (a) an Euler circuit? (b) a Hamiltonian circuit? Justify your answers.

Problem 46E Prove Corollary Corollary Let G be a graph, and let v and w be two distinct vertices of G. There is an Euler trail from v to w if, and only if, G is connected, v and w have odd degree, and all other vertices of G have positive even degree.

Problem 41E Prove that if there is a trail in a graph G from a vertex v to a vertex w, then there is a trail from w to v.

Problem 42E If a graph contains a circuit that starts and ends at a vertex v, does the graph contain a simple circuit that starts and ends at v? Why?

Problem 44E Let G be a connected graph, and let C be any circuit in G that does not contain every vertex of C. Let G’ be the subgraph obtained by removing all the edges of C from G and also any vertices that become isolated when the edges of C are removed. Prove that there exists a vertex v such that v is in both C and G’.

Problem 45E Prove that any graph with an Euler circuit is connected.

Problem 48E Problem For what values of m and n does the complete bipartite graph on (m, n) vertices have (a) an Euler circuit? (b) a Hamiltonian circuit? Justify your answers.

Problem 49E What is the maximum number of edges a simple disconnected graph with n vertices can have? Prove your answer.