Week 2

Question 1

What is r-Connectivity?

Answer 1

Question 2

What is a Harry Graph?

Answer 2

Question 3

How to construct a Harary Graph if r and n is even?

Answer 3

Question 4

How to construct a Harary Graph if r odd and n is even?

Answer 4

Question 5

How to Harary Graph construct both r and n are odd?

Answer 5

Question 6

What is the definition of vertex independent?

Answer 6

Question 7

What is the definition of edge-independent?

Answer 7

Question 8

What is Menger’s theorem?

Answer 8

Question 9

What is the definition of Biparte graph?

Answer 9

Question 10

What is the definition of a ranked embedding?

Answer 10

Question 11

What is the theorem about biparte, and ranked embedding?

Answer 11

Question 12

What is the definition of a planar graph?

Answer 12

Question 13

What is Euler’s theorem?

Answer 13

Question 14

What is a theorem about a planar graph with n ≥ 3 and m edges?

Answer 14

Question 15

What is a theorem about a planar graph and one vertex v, with delta(v)?

Answer 15

Question 16

What is a directed graph?

Answer 16

Question 17

What is the indegree and outdegree of a vertex?

Answer 17

Question 18

What is a theorem about the indegree and outdegree?

Answer 18

Question 19

What is the difference when storing a undirected graph and directed graph in an adjecency list?

Answer 19

Question 20

What is the goal of edge coloring?

Answer 20

Question 21

What is the definition and notation of an r-edge coloarable edge?

Answer 21

Question 22

What is the definition of Δ(G)?

Answer 22

Question 23

What is a theorem of ϗ’(G)?

Answer 23

Question 24

What is the definition of r-vertex colorable?

Answer 24

Question 25

Proof that:

Answer 25

Question 26

What is the maximum number of colors needed for a planar graph?

Answer 26

4

Question 27

How to show that a most 5 colors are needed to color a planar map?

Answer 27

Proof by induction on the number of vertices of G.
Basecase. If n = 2, we can color the vertices of G with 2 colors and 2≤5.

Induction hypothesis. Assume any planar graph with at most n vertices can be “vertex colored” with ≤ 5 colors.

Inductive step. We have to show that any planar G with n + 1 vertices can be “vertex colored” with ≤ 5 vertices.

• Take an arbitrary graph G with n + 1 vertices.
• G has at least one vertex, say v, with degree ≤ 5. Why?
• Let G∗ = G − {v}. The vertices of G∗ can be colored with ≤ 5 colors, by induction hypothesis. Assume c1, . . . , c5 are the colors used in G∗.
• If |N(v)| ≤ 5, then v can be colored with an unused color and we’re done. - So, we assume that N(v) = 5 all 5 colors are used by N(v).
• Let N (v) = {v1, v2, . . . , v5}, clockwise around v, and color(vi) = ci.

Case 1. Assume that no [v1, v3]-path in G∗ has only colors c1 and c3.

• Let H be the subgraph induced by all (v1, w)-paths in G∗ that have only colors c1 and c3. (Suppose the following path is one of them.)
• Vertex v3 and its neighbor are not in H. Why?
• Interchanging c1 and c3 in H doesn’t violate the “proper coloring” of G∗.
• v1’s color becomes (and v3’s color is still) c3, so v can be colored with c1.

Case 2. Some [v1, v3]-path P in G∗ has only colors c1 and c3. Since G is planar, the cycle [P, v, v1] in G encloses either v2 or v4.

v1 v5

v

v2 v3

v4
- This implies that there is no [v2, v4]-path in G∗ with only colors c2 and c4.

• Let H′ be the subgraph induced by all (v2,w)-paths in G∗ that have only colors c2 and c2.
• Vertex v4 and its neighbor are not in H′.
• Interchanging c2 and c4 in H′ doesn’t violate the “proper coloring” of G∗.
• v2’s color becomes (and v4’s color is still) c4, so v can be colored with c2.