Graph

Theory

Graph - In MA010 graph is a pair G = (V,E) s.t. $E \subseteq {V \choose 2}$.

Subgraph - H is subgraph of G iff V(H) ⊆ V(G) and E(H) ⊆ E(G).

Subdivision - H is a subdivision of G iff it can be obtained by edge subdivision meaning adding vertex w and replacing uv by uw and wv (obtained by replacing subset of edges by paths).

Spanning subgraph - H is a spanning subgraph of G iff V(H) = V(G) and E(H) ⊂ E(G).

Induced subgraph - H is induced subgraph of G iff V(H) ⊆ V(G) and E(H) = V(H) ∩ E(G).

Minor - H is a minor of G iff it can be obtained from G by

1. vertex deletion (on v → V′ = V \ v and E′ = {e|e ∈ E ∧ v ∉ e})
2. edge deletion (on e → E′ = E \ e)
3. edge contraction (on u, v → V′ = (V\{u,v}) ∪ z and
   E′ = {e|e∈E∧v,u∉e}∪{{z,w}|w ∈ n_G(u) ∪ n_G(v)})

Isomorphism - Bijection φ : V(G) → V(H) between G and H is an isomorphism iff xy ∈ E(G) ⇔ φ(x)φ(y) ∈ E(H).

Clique-number ω(G) - vertex size of the largest subgraph H s.t. H is a complete graph.

Chord - an edge uv s.t. u and v belong to a cycle but uv does not.

Chordal graph - A graph G is chordal if ∀n ≥ 4 graph G does not contain C_n as induced subgraph.

Perfect graph - A graph G is perfect if every induced subgraph H of G satisfies χ(H) = ω(H).

Walk - a sequence of vertices v₁v₂v₃...v_k s.t. v_iv_i + 1 is an edge for every i ∈ [k−1].

Path - is a walk with no vertex twice.

Tour - is a walk with no edge twice.

Theorems and Lemmas

Handshaking Lemma: For every graph G = (V,E) we have ∑_v ∈ Vdeg(v) = 2|E|

Lemma 2: For any graph G the number of v s.t. deg(v) is odd is even.

Fact 1: If there is a walk between u and v there is a path from u to v.

Trees and forests

Forest - a graph G is a forest if it does not contain a subgraph isomorphic with a cycle.

Tree - a graph G is a tree iff it is forest and it is connected.

Theorems, Lemmas, facts

Equality - The following statements are equal:

1. G is connected and has no cycle.
2. G is connected and removing any edge disconnects G.
3. G has no cycle and ∀uv ∉ E(G).{G + uv has a cycle}.
4. ∀u, v ∈ V(G), ∃! path between u and v
5. G is connected and has |V(G)| − 1 edges.

Directed graph

Directed graph - a pair G = (V,E) s.t. E ⊆ V × V.

Oriented graph - graph G is oriented, if it was obtained from undirected graph by orienting its edges, meaning it is directed, but it does not contain loops or bigons.

Loop - an edge (v,v)

Bigon - pair of edges (u,v) and (v,u).

Head - in oriented edge uv (u to v) vertex v is called head.

Tail - in oriented edge uv (u to v) vertex u is called tail.

Planar graph

Planar graph - A graph G is planar iff there exists a drawing in the plane ℝ² without edge crossings. Meaning there exists a function φ : V(G) → ℝ² and function φ_uv : [0,1] → ℝ² for every uv ∈ E(G) s.t. φ_uv is injective, continous. The φ(V(G)) and all φ_uv((0,1)) are pairwise disjuncitve.

Plane graph - A planar graph together with a plane embedding.

Face - maximal arc-connected region which does not contain a point of the drawing.

Triangulation - plane graph s.t. every face is bounded by a C₃.

Near-triangulation - is a plane graph with all faces except for the outer face bounded by a triangle and the outer face bounded by a cycle.

Platonic solid - polyhedron s.t. all faces are congruent regular polygons and the same number of faces meets at each vertex.

Facial walk - minimal face bounding walk.

Dual-graph - The dual graph G* of a plane graph G is a graph in which: the vertices of G* one-to-one correspond to the faces of G and two vertices of G* are adjacent if the corresponding faces share an edge.

Theorems, Lemmas and Facts

Fact - If G is connected plane graph, then every face is bounded by a closed walk. Minimal such walk is called a facial walk.

Fact 2 - K_3, 3 and K₅ are not planar.

Euler’s formula - Let G be a connected plane graph with n vertices m edges and f faces. Then n − m + f = 2

Theorem 1 - Let G be a plane graph with n ≥ 3 vertices, then there exists a triangulation H s.t. G is a spanning subgraph of H.

Corollary - If G is a planar graph with n ≥ 3 vertices, then e ≤ 3n − 6.

Corollary - If G is a planar graph with n ≥ 3 vertices, then there exists a vertex v s.t. deg(v) ≤ 5.

Wagner’s Theorem - A graph G is planar iff G does not contain K_3, 3 or K₅ as a minor.

Kuratowski’s Theorem - A graph G is planar iff G does not contain a subgraph that is a subdivision of K₅ or K_3, 3.

Coloring

k-coloring - function c : V(G) → {1, ..., k} s.t. uv ∈ E(G) ⟹ c(u) ≠ c(v).

Chromatic number χ(G) - chromatic number of graph G is the smallest k s.t. there exists a k-coloring for G.

k-edge-coloring - function c : E(G) → {1, ..., k} s.t. e, f ∈ E(G) ∧ e ≠ f ∧ e ∩ f ≠ ∅ ⟹ c(e) ≠ c(f).

Chromatic index χ′(G) - chromatic index of graph G is the smallest k s.t. there exists a k-edge-coloring for G.

k-list-assignment - a function L : V(G) → 2^ℕ s.t. ∀v ∈ V(G).{|L(v)| = k}.

L-colorable - Graph G is L-colorable if ∃c : V(G) → ℕ s.t. c is a valid vertex coloring and ∀u ∈ V(G).{c(u) ∈ L(u)}.

list chromatic number χ_l(G) - the smallest k s.t. for all k-list-assignments L, graph G is L-colorable.

Theorems, Lemmas, Facts

Bounds of chromatic number: ω(G) ≤ χ(G) ≤ Δ(G) + 1.

Bounds of chromatic index: Δ(G) ≤ χ′(G) ≤ Δ(G) + 1.

Bounds of list chromatic number: χ(G) ≤ χ_l(G) ≤ Δ(G) + 1.

Theorem: Every plane triangulation is 4 − colorable ⇔ Every cubic bridgless plane graph is 3-edge-colorable.

Brook’s Theorem: Let G be a connected graph. If G is not an odd cycle or a complete graph, then χ(G) ≤ Δ(G).

Vizing’s Theorem: χ′(G) ≤ Δ(G) + 1.

Thomassen’s Theorem: For every planar graph G, χ_l(G) ≤ 5.

Voigt’s Theorem: There exists a planar graph G s.t. χ_l(G) > 4.

Fact 2: If G is a chordal graph, then χ(G) = ω(G).

Theorem (Chudnovsky, Robertson, Seymar, Thomas): A graph G is perfect if it does not contain an odd cycle or a complement of an odd cycle as an induced subgraph.

Connectivity

Connected - a graph is connected iff for every u and v there exists a walk from u to v.

k-edge-connected - if removal of  ≤ k − 1 edges cannot disconnect G. ∀F ⊆ E(G).{|F| ≤ k − 1 ⟹ G \ F is connected}.

k-vertex-connected - graph G is k-vertex-connected if |G| ≥ k + 1 and ∀W ⊆ V(G).{|W| ≤ k − 1 ⟹ G \ W is connected}.

Bridgless graph - a graph G is bridless iff ∄e ∈ E(G) s.t G \ e has more components than G (graph G is 2-edge-connected).

Theorems, Lemmas, Facts

Menger’s Theorem: A graph G is k-edge-connected ⇔ ∀u, v ∈ V(G).∃k edge-disjoint paths from u to v.

Menger’s Theorem: A graph G is k-vertex-connected ⇔ ∀u, v ∈ V(G).∃k internally vertex-disjoint paths from u to v}.

Theorem: A graph G is 2-connected iff G can be obtained from K₃ = C₃ by the following two operations: add an edge, subdivide an edge.

Theorem: A graph G is 3-connected iff G can be obtained from K₄ by the following operation G → G′: pick a vertex v, replace it with v′v″ s.t. n_G(v) = n_G′(v′) ∪ n_G′(v″) and ∀v ∈ G′.{deg(v) ≥ 3}.

Flow networks

Network - directed graph together with a function c : E(G) → ℝ₀⁺ and two special vertices labeled as source and sink.

Flow - A flow in network G is a function f : E(G) → ℝ₀⁺ s.t.

1. ∀e ∈ E(G).{f(e) ≤ c(e)}
2. ∀v ∈ V(G).{v is sink or source  ∨ ∑_e → vf(e) = ∑_v → ef(e)}

Value of flow - |f| = ∑_{source → e}f(e) − ∑_{e → source}f(e) = ∑_{e → sink}f(e) − ∑_{sink → e}f(e)

Cut - Partition of V(G) to sets A and B s.t. source ∈ A and sink ∈ B. The size of the cut is ∑_{e : A → B}c(e).

Optimal flow - flow f s.t. |f| = sup_f′|f′|.

Augmenting path - a path u = v₁, v₂, ..., v_n = v from u to v is in context of flow networks called augmenting if it contains edges e = v_iv_i + 1 s.t. {(v_i,v_i + 1) ∈ E(G) ∧ f(e) < c(e)} ∨ {(v_i + 1v_i) ∈ E(G) ∧ f(e) > 0}

Matching - An edge set M ⊆ E s.t. ∀e, f ∈ M.{e ∩ f = ∅}.

Perfect Matching - A matching M s.t. ∀v ∈ V(G)∃e ∈ M.{v ∈ e}.

Vertex cover - vertex set W ⊆ V s.t. ∀e ∈ E.{e ∩ W ≠ ∅}.

Theorems, Lemmas, Facts

Fact - ∀f∀cut(A,B).{|f| ≤ |cut(A,B)|}.

Max-flow Min-cut Theorem - max_f|f| = min_cut(A,B)|cut(A,B)|

Fact - ∀cut(A,B).{|f| = ∑_{e : A → B}f(e) − ∑_{e : B → A}f(e)}

Fact - A flow f is optimal iff there is no augmenting path.

Ford–Fulkerson - greedy algorithm that computes the maximum flow in a flow network using augmenting paths.

Fact - size of any matching ≤ size of any vertex cover

Kőnig’s Theorem - In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

Hall’s Theorem - Given set set Ξ = {X₁, X₂, ..., X_n} there exists a system of distinct representatives x₁ ∈ X₁, x₂ ∈ X₂, …, x_n ∈ X_n s.t. all x₁, x₂, ..., x_n are pairwise distinct iff ∀Y ∈ 2^Ξ.{|Y| ≤ |⋃_X ∈ YX|}

P NP

P class - class of decision problems s.t. there exists an algorithm, which can solve the problem in polynomial time.

NP class - class of decision problems s.t. there exists an algorithm, which can “verify” the solution, in polynomial time.

Polynomial-time reduction - Q≤_PR if there exists a algorithm A s.t. ∀x.{x ∈ Q ⇔ A(x) ∈ R}.

NP-complete - problem Q is NP-complete iff Q ∈ NP and all NP problems can be reduced to Q in polynomial time.

Theorems, Lemmas, Facts

NP-complete problems - Here is a list of some NP-complete problems:

1. 3-SAT - satisfiability of a CNF F where each clause has three literals.
2. 3-COL - 3-colorability of a graph G.
3. VCOVER - Existence of a vertex cover of size  ≤ k in graph G.
4. 5-3-COL - 3-colorability of a graph G s.t. ∀v ∈ V(G).deg(v) ≤ 5
5. 4-3-COL - 3-colorability of a graph G s.t. ∀v ∈ V(G).deg(v) ≤ 4
6. INSET - Existence of a independent set of size  ≥ k in graph G.

Π₂^P-complete problems - List of some Π₂^P-complete problems problems:

1. 3-LCOL - 3-list-colorability of a graph