Sale!

Applied Graph Theory Homework 10

$30.00

Category:
Rate this product

EECS 455: Applied Graph Theory
Homework 10

The next subject we will cover is plane graphs. The questions below cover Euler’s Formula and duals of
plane graphs. Also take a look at Kuratowski’s Theorem.
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.

Applied Graph Theory Homework 10
$30.00
Open chat
Need help?
Hello
Can we help?