[Solved] CSDS455 Homework 10

Problem 1: Prove Euler’s Formula using induction on the number of vertices and edges of G. (The Diestel book gives an induction only on edges.)

Problem 2: Prove that every connected plane graph has a vertex with degree less than 6.

Problem 3: Prove that a set of edges in a connected plane graph G forms a spanning tree of G if and only if the duals of the remaining edges form a spanning tree of G^∗.

Problem 4: Let G and G^∗ be mutually dual plane graphs. Prove that if G is 2-connected then G^∗ is

2-connected.