Simplicial Maps and Contractions 1. Give a contraction C, to C3. Answer: 2. Give a surjective...

Transcribed Image Text:

Simplicial Maps and Contractions 1. Give a contraction C, to C3. Answer: 2. Give a surjective simplicial map C, to C3 that is not a contraction. Answer: Contracting Edges in Planar Graphs 3. Let G be a planar graph with n vertices, m edges, and f faces. Let e e EG be an edge of G. How many vertices, edges, and faces can G = G/e have? This is the graph G with the edge e contracted. Please give your answer as a collection of (n', m', f') triples. Answer: Forbidden Minors 4. Let Ho,..H-1 be a set of graphs. Let S be the set of graphs G such that for all i e [k), H, M G. Let GE S and let G' be a minor of G. Prove that G e S. Answer: Planar 3-connected graphs 5. Let G be a planar 3-connected graph. Let H = G +e still be a planar graph where e is an edge. Show that H contracts to G*. Note that H is the dual of H. Answer: Simplicial Maps and Contractions 1. Give a contraction C, to C3. Answer: 2. Give a surjective simplicial map C, to C3 that is not a contraction. Answer: Contracting Edges in Planar Graphs 3. Let G be a planar graph with n vertices, m edges, and f faces. Let e e EG be an edge of G. How many vertices, edges, and faces can G = G/e have? This is the graph G with the edge e contracted. Please give your answer as a collection of (n', m', f') triples. Answer: Forbidden Minors 4. Let Ho,..H-1 be a set of graphs. Let S be the set of graphs G such that for all i e [k), H, M G. Let GE S and let G' be a minor of G. Prove that G e S. Answer: Planar 3-connected graphs 5. Let G be a planar 3-connected graph. Let H = G +e still be a planar graph where e is an edge. Show that H contracts to G*. Note that H is the dual of H. Answer: