Chapter 9

Question 1

Def/ A graph G is planar if:

Answer 1

if it is isomorphic to a graph that can be drawn w/o edge crossings.

Question 2

Thm: Planar graphs can be drawn with what type of lines?

Answer 2

Straight lines

Question 3

Def/ Regions are:

Answer 3

Regions are connected areas of the plane subdivided by edges in a planar graph.

Question 4

Thm/ Euler’s Formula: In A connected planar graph with p vert., q edges, r regions, p-q+r=2.

Answer 4

Pf induct on edges. Single vertex, p=1, q=0,r=1, thus 1+1=2 holds.
Induct: SUppose true for all planar graphs with k-1 edges. Let G be conn. planar graph w/ K edges. If G is a tree, q=p-1, r=1, so holds.
If not a tree, there is a cycle C. Then, consider e edge on C and remove it. Then, edges of G-e are k-1, p=p, regions = r-1. By hyp, we know that p - (k-1) + (r-1) = 2. Thus,
p-k+1+r-1=2,
=> p-k+r=2 holds, where these values are for G which has size K.

Question 5

Thm: Let G conn. planar graph, p vert., q edges, and p >=3. Then, q<=3p-6.

Answer 5

Let N be the sum of edges surrounding or in each region summed across all regions. Since some may be double counted,
N <= 2q
Since there are >=3 edges/region, N >= 3r
2q >= N >= 3r
=> r <= (2/3)q
Since 2 = p-q+r <= p-q+(2/3)q
=>2 <= p-(1/3)q
=> q <= 3p-6

Question 6

Corr: K5 is not planar:

Answer 6

Because q<=3p-6 does not hold,
25 <=3(10)-6 is not true

Question 7

Thm: If G is planar, connected, bipartite then q <= 2p-4

Answer 7

Proof: Let N be the sum of all edges over every region, thus maxing out at double count N <= 2q.
Since smallest cycle is 4 (bipartite cycles all are even, and 2 is not a cycle), then N >= 4r
=> r <= q/2
Plug into Euler’s formula of p-q+r = 2
=> 2 <= p-q + q/2
=> q <= 2p-4

Question 8

Corr: K3,3 is not planar:

Answer 8

Because q <= 2p - 4 doesn’t hold.
9 <= 6-4 is not true

Question 9

Defn/ A subdivision of a graph is:

Answer 9

A subdivision of a graph is a new graph obtained by adding vertices along edges

Question 10

Note for subdivisions: A subdivision of G is planar IFF G planar.
If G planar, so is any subgraph

Answer 10

obviously

Question 11

Thm: (Kurotowski) A graph G is not planar IFF it contains a subgraph isomorphic to a subdivision of K3,3 or K5

Answer 11

Check if we even prove this shit

Question 12

Thm: Let G connected, if E(G) <= V(G) + 2, than G is planar.

Answer 12

Pf/ BWOC, suppos G is not planar. Let H be spanning tree, thus V(H) = V(G), and E(H) = V(H) -1
By Kura. it has subdiv. of K33 or K5.
Case 1: Subdiv. of K5 is in G, involving m vert and n edges.
Since K5 has 5 vert., 10 edges, n-m=5 (even if you subdivide, still holds).
Since max, m-1 edges can be in H (one less than number of vert. bc its a tree), we would need to add at least 6 edges to H to get G b/c edges of G is >=10 and you have >=4 edges in H.
=> E(G) >= E(H) + 6 = V(G) + 5 by applying above. Thus contradict original statement.
Case 2: If G has a subdivision of K33, with m vert, n edges.
n-m=3. By similar, must add at least 4 edges to H to produce G.
=> E(G) >= E(H) + 4 = V(G) + 3 Thus contradiction

Question 13

Defn/ A coloring of a graph:

Answer 13

assigns “colors” to each vertex s.t. adjacent vertices have different colors

Question 14

Def/ A chromatic number Chi(G) is:

Answer 14

A chromatic number Chi(G) is the min. size of a coloring set to color G

Question 15

Thm: Chi(G) <= 1 + Del(G), where Del(G) is the max vert. degree.

Answer 15

Pf by induction on order. If p=1, 1<= 1+0 b/c Chi(G) = 1, Del(G) = 0.
Induct on p: Assume true for all order k-1 graphs G’, Chi(G’) <= 1+ Del(G’)
Let G be graph of order K, let v be any vertex. Let G’ = G-v, s.t. G’ satisfies the induct. hypoth.
Case 1: Del(G-v) = Del(G) AKA didn’t affect max degree.
So, add v anywhere and some color from G-v can be used because its only connected to V(G)-1 vert. at max.
Case 2: Del(G-v) < Del(G):
May introduce another color for v, obtaining a coloring for G w/ no more than 1 + Del(G) colors.

Question 16

Def/ A graph is k-partite if:

Answer 16

if V(G) can be partitioned into sets v1,v2,…,vk s.t. every edge is betw/ vert. in different partitions.

Question 17

Thm: A graph is k-partite IFF it is k-colorable

Answer 17

If K-colorable, there exists a patition s.t. edges cannot be between vertices in the same partition.
Other way - homework example, FILL OUT LATER

Question 18

Lemma: The number of edges in an order p k-partite grap is: q <= (k(k-1)/2) * (p/k)^2 From worst case scenario where every partition is same size connecting to each vertex.

Answer 18

Pf/ The number of edges possible is SUM(SUM(|vi||vj|), so summing each size of partitions multiplied together. Shorthand for max connections, subject to sum(|vi|) = p, AKA all partitions added equals p (Duh).
Maximized where vi=p/k.

Question 19

Corr: Chi(G) >= p^2 / (p^2 - 2q) for K-partite graphs

Answer 19

Pf/ from thm, sub in Chi(G) for K in k-partite graphs because they require k-colorings.
=> q <= [Chi(G)( Chi(G)-1 )/2] * (p/Chi(G))^2
=> rearrange to get Chi(G) >= p^2/ (p^2 - 2q)

Question 20

Lemma: Every connected planar graph has a vertex of degree 5 or less.

Answer 20

BWOC, suppose not. degv >=6, for all vertices. Sum of degrees is 2q because each edge contributes 2 to sum of deg.
Thus, sum of degrees is >= 6p because degv >= 6, so 2q >= 6p.
However, prev thm says q <= 3p-6, so contradiction.

Question 21

Thm: If G planar, then Chi(G) <= 5

Answer 21

Induct on order: SUppose all planar graps of order k-1 have Chi(G) <= 5.
Let G be graph of order K, let v be vertex of degv<=5.
If deg<=4, exists a color which is not from adj. vertex. Worst case, all adj. have diff colors so we have to recolor.
Case 1: There is no v1-v3 path (two non-near vert. connected to v). So then we can swap color of v1 to v3’s color and it won’t run back into itself.
Case 2: There does exist a v1v3 path using colors 1 and 3. Then by planarity, there is no v2v4 path, so we can swap v2’s color for v4’s color and we have freed up a color.