Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Math 154 Homework 4

Fall 2021

        This homework is due on gradescope by Friday October 22nd at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in LATEXis recommend though not required.

        Please cite any other students with whom you collaborated on any problems.

Question 1 (Infinite Semi-Eulerian Graphs, 80 points). Define a semi-infinite trail on a graph G to be a sequence of vertices v1, v2, v3, . . . so that for each i there is an edge in G between vi and vi+1 and so that these edges are all distinct. Call G semi-Eulerian if there exists such a trail that uses every edge of G exactly once. For this problem, we will consider graphs G with infinitely many vertices and edges for which each vertex is incident on only finitely many edges (and thus has a well defined degree).

(a) Show that if G has a semi-infinite Eulerian trail starting at a vertex v, then deg(v) is odd and all other degrees in G are even, and that G is connected except for isolated vertices. [20 points]

(b) Unfortunately, the conditions in (a) are not sufficient. Give an example of a graph G with a vertex v of odd degree and all other degrees even so that G does not have a semi-Eulerian trail. [20 points]

(c) Show that any graph G with a semi-infinite Eulerian trail must satisfy the following property: If G′ is any subgraph of G obtained by removing finitely many edges of G, G′ contains only one connected component of infinite size. [20 points]

(d) It turns out that the conditions in (a) and (c) together are sufficient. The proof relies on the following Lemma: Suppose G is a graph with only one vertex v of odd degree and satisfying the condition in (c). If P is any finite path starting at v, then the edges of all of the finite connected components of G − P can be partitioned into circuits. Prove this lemma. [20 points]

Question 2 (Toughness of Hamiltonian Graphs, 20 points). Let G be a Hamiltonian graph and let {v1, v2, . . . , vk} be a set of k vertices of G for some k ≥ 1. Let G′ be the subgraph of G obtained by removing all of the vertices vi and all of their edges from G. Prove that G′ has at most k connected components.

Question 3 (Extra credit, 1 point). Approximately how much time did you spend on this homework?