Question

1.Can you apply Theorem 13.6.12(A Vertex of Degree Five. If GG is a connected planar graph, then it has a vertex with degree 5 or less.) to prove that the Three Utilities Puzzle can’t be solved? 2.  Prove that if an undirected graph has a subgraph that is a K3K3 it then its chromatic number is at least 3.

Answer 1

1)

Theorem 13.6.12. A Vertex of Degree Five.

If GG is a connected planar graph, then it has a vertex with degree 5 or less.

Proof.

(by contradiction): We can assume that GG has at least seven vertices, for otherwise, the degree of any vertex is at most 5. Suppose that GG is a connected planar graph and each vertex has a degree of 6 or more. Then, since each edge contributes to the degree of two vertices, e≥6v2=3v.e≥6v2=3v. However, Theorem 13.6.10 states that the e≤3v−6<3v,e≤3v−6<3v, which is a contradiction.

Theorem 13.6.10. A Bound on Edges of a Planar Graph.

If G=(V,E)G=(V,E) is a connected planar graph with vv vertices, v≥3,v≥3, and ee edges, then

e≤3v−6(13.6.2)(13.6.2)e≤3v−6

Proof.

(Outline of a Proof)

1. Let rr be the number of regions in G.G. For each region, count the number of edges that comprise its border. The sum of these counts must be at least 3r.3r. Recall that we are working with simple graphs here, so a region made by two edges connecting the same two vertices is not possible.

2. Based on (a), infer that the number of edges in GG must be at least 3r2.3r2.

3. e≥3r2 ⇒ r≤2e3e≥3r2 ⇒ r≤2e3

4. Substitute 2e32e3 for rr in Euler's Formula to obtain an inequality that is equivalent .