## Graph Theory

2018-11-10 08:00 CST
2019-12-22 15:33 CST
CC BY-NC 4.0

## Introduction

• order: vertices in G
• trivial graph: order 1
• labeled graph
• word graph
• incident: u and v are neighbors, then u and v are incident with each other
• proper subgraph: E or V is different
• spanning graph: same vertex as G
• induced graph: if u and v are vertices of F and uv is an edge in G, then uv is in F
• edge-induced subgraph
• walk: W = (u=v0, v1, ..., vk = v)
• open walk: u!=v
• closed walk: u==v
• trail: u-v walk in which no edge is traversed more than once
• path: u-v walk in which no vertices are repeated
• circuit: a closed trial of length 3 or more
• cycle: a circuit that repeats no vertex, except for the first and last
• component
• geodesic: a u-v path of length d(u,v)
• complement
• $K_n$ : complete graph
• $P_n$ : path (graph)
• $C_n$: circle (graph)
• bipartite graph: contains no odd cycle
• $K_{s,t}$: complete bipartite graph
• star: $K_{1,t}$ or $K_{s,1}$
• k-partite graph
• complete k-partite graph (complete multipartite graphs)
• union: $G_1 \cup G_2$
• join: $G+H$ consists of $G\cup H$ and all edges joining a vertex of G and a vertex of H.
• Cartesian product $G * H$: V($GH$) = V($G$) $$V(H), two distinct vertices (u,v) and (x,y) are adjacent if u=x,vy\inE(H) or v=y,ux\inE(G) • n-cubes (hypercubes): Q_n = Q_{n-1} * K_2, Q_1 = K_2 • multigraph • parallel edges: join the same pair of vertices • pseudograph: edge can join u and u which is a loop • digraph (directed graph): directed edges • adjacent to: (u,v) • adjacent from: (u,v) • oriented graph: at most one of (u,v) and (v,u) is a directed edge • oritentation of G ## Degrees • degree: the number of edges incident with v • N(v): the neighborhood of v • isolated vertex: deg_G(v)=0 • \delta(G): minimum degree of G • \Delta(G): maximum degree of G • The First Theorem of Graph Theory: \sum_{v\in V(G)} deg(v) = 2|E| • r-regular graph: \delta(G) = \Delta(G) = r • cubic graph: 3-regular graph (K_4, K_{3,3}, Q_3, Petersen graph) • Petersen graph • H_{r,n}: Harary graphs, r-regular graph of order n if at least one of r and n is even • degree sequence • graphical: a finite sequence is a degree sequence of some graph • Havel-Hakimi Theorem: non-increaing sequence s:d_1,d_2,...,d_n where d_1\geq 1 is graphical iff s_1:d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n is graphical. ## Isomorphic Graphs • isomorphic: exists a one-to-one \phi from V(G) to V(H) such that uv\in E(G) and \phi(u)\phi(v)\in E(H) • self-complementary: G \equiv (\overline H) ## Trees • bridge: G is connected, G-e is disconnected • acyclic graph: no cycles • tree: acyclic connected graph • rooted tree • forests • w(H): sum_{e\in E(H)}w(e) • spanning tree of G • cycle property • cut property • Kruskal's Algorithm • Prim's Algorithm • Carley's Theorem: the spanning tree of complete graph of order n is n^{n-2} • Matrix Tree Theorem: The spanning tree of an arbitrary graph is any cofactor of matrix C$$\left[\begin{matrix} \deg v_1 & -a_{12} & ... & -a_{1n}\
-a_{21} & \deg v_2 & ... & -a_{2n}\
\vdots & \vdots & \ldots & \vdots\
-a_{n1} & -a_{n2} & ... & \deg v_n \end{matrix}\right]

## Connectivity

• cut-vertex: G is connected and G-v is disconnected
• nonseparable graph: a nontrivial connected graph with no cut-vertices
• block: a maximal nonseparable subgraph of G
• vertex-cut: a set U of vertices of G such that G-U is disconnected
• minimum vertex-cut
• $\kappa(G)$: vertex-connectivity, the cardinality of a minimum vertex-cut; also the maximum number of disjoint u-v path for which u and v are connected
• k-connected: $\kappa(G)\geq k$
• Theorem: 2-connected $\iff$ any 2 adjacent edges of G lie on a common cycle of G
• edge-cut
• minimum edge-cut
• $\lambda(G)$: edge-connectivity
• k-edge-connected
• Theorem: $\kappa(G)\leq\lambda(G)\leq\delta(G)$
• u-v separating set: the set separate G
• minimum u-v separating set
• internal vertex of u-v path P: a vertex of P different from u and v
• internally disjoint: A collection of u-v paths that every two of them have no vertices in common other than u and v
• Menger's Theorem: minimum cardinality of u-v separating set = maximum number of internally disjoint u-v paths in G
• Whitney's Theorem: k-connected iff for each pair u, v there are at least k internally disjoint u-v paths

## Traversability

• Eulerian circuit: a circuit contains every edge of G
• Eulerian graph: graph G contians an Eulerian circuit
• Eulerian trail: an open trail that contains every edge of G
• $K\ddot{o}nigsberg$ Bridge Problem
• Theorem: A nontrivial connected graph G is Eulerian iff every vertex of G has even degree
• Theorem: A connected graph G contains an Eulerian trail iff exactly two vertices of G have odd degree.
• Hamiltonian cycle: a cycle in a graph G that contains every vertex of G
• Hamiltonian graph
• Hamiltonian path: a path in G contains every vertex of G
• $k(G)$: number of components in G
• Theorem: For Hamiltonian Graph, $k(G-S)\leq|S|$
• Theorem: $n\geq3$, if $degu+degv\geq n$ for each pair u,v of nonadjacent vertices of G, then G is Hamiltonian
• closure C(G): the graph obtained from G(order n) by recursively joining pairs of nonadjacent vertices whose degree sum is at least n until no such pair remains
• Theorem: A graph is Hamiltonian iff C(G) is Hamiltonian

## Matching

• independent: a set of edges in which no two edges are adjacent
• matching: an independent set of edges in G
• $N(X)$: neighborhood of X
• Hall's condition: $|N(X)|\geq|X|$ for every nonempty subset X of U
• Theorem: Let G be a partite graph with partite sets U and W such that $r=|U|\leq|W|$. Then G contains a matching of cardinality r iff G satisfies Hall's condition.
• a system of distinct representatives
• perfect matching: a graph of order 2k has a matching M of cardinality k
• Theorem: Every r-regular bipartite graph has a perfect matching
• maximum matching: $|M| = \alpha'(G)$
• edge independence number $\alpha'(G)$: the maximum cardinality of an independent set of edges
• cover: a vertex and an incident edge are said to cover each other
• edge cover: a set of edges of G that covers all vertices of G
• edge covering number $\beta'(G)$: cardinality of minimum edge cover
• vertice independence: no two vertices in the set are adjacent
• vertice independence number $\alpha(G)$: maximum cardinality of an independent set of vertices in G
• maximum independent set
• vertex cover
• vertex covering number $\beta(G)$
• minimum vertex cover
• Theorem: Gallai Identity: For every graph G of order n containing no isolated vertices, $\alpha'(G)+\beta'(G)=n, \alpha(G)+\beta(G)=n$
• Konig Theorem: If G is a bipartite graph then $\alpha'(G)=\beta(G)$

## Factorization

• $k_o(G)$: the number of odd components of a graph G.
• factor-factorization-factorable
• 1-factorization: there exists 1-factors $F_1, F_2, \cdots, F_r$ of G such that ${E(F_1),E(F_2),\cdots,E(F_r)}$ is a partition of $E(G)$ (e.g. $K_{2k}$,r-regular bipartite graph)
• Petersen's Theorem: Every 3-regular bridgeless graph contains a 1-factor
• cyclic factorization
• Theorem: G is 2-factorable iff G is r-regular for some positive even integer r
• Hamiltonian factorization
• Theorem: For every integer $k\geq1$, $K_{2K+1}$ is Hamiltonian-factorable
• Theorem: For every integer $k\geq1$, $K_{2K}$ can be factored into k-1 Hamiltonian-cycles and a 1-factor
• F-factorable: G is factorable into factors $F_1, F_2,\dots, F_k$ if ${E(F_1),E(F_2),\dots,E(F_k)}$ is a partition of $E(G)$. Each factor $F_i$ is isomorphic to some graph $F$.
• Kirkman's Schoolgirl Problem
• Kirkman triple system: exists iff $n\equiv3(mod\ 6)$
• decomposable: A graph is decomposable into the subgraphs $H_1,H_2,\dots,H_k$ if ${E(H_1),E(H_2),\dots,E(H_k)}$ is a partition of E(G).
• decompsition-decomposable
• H-decomposable and H-decomposition: $H_i$ is isomorphic to some graph H
• graceful labeling: a one-to-one function $f:V(G)\rightarrow{0,1,2,\dots,m}$ is a graceful labeling if the induced edge labeling $f'(e)=|f(u)-f(v)|$ is one-to-one.
• graceful graph: G possessing a graceful labeling
• Conjecture: Every tree is graceful
• Instant Insanity
• girth: the length of a smallest cycle in a graph
• g-cage: a 3-regular graph of minimum order that has girth $g\geq3$ (for $g\leq8$, the g-cages are all sole, $K_4,K_{3,3}$,Petersen,Heawood,McGee,Tutte-Coxeter)
• Petersen Graph
• counter-example to 'Every 3-regular bridgeless graph is 1-factorable'
• The only 5-cage

## Distance

• distance: positive; reflexivity; symmetric; triangle inequatity
• metric space: (V(G), d)
• $e(v)$: eccentricity, the distance between v and a vertex farthest from v in G
• $rad(G)$: radius, $min_{v\in V(G)}e(v)$
• $diam(G)$: diameter, $max_{v\in V(G)}e(v)$
• $Cen(G)$: central vertex, e(v)=rad(G)
• self-centered: Cen(G) = G
• Theorem: $rad(G)\leq diam(G) \leq 2rad(G)$
• $Per(G)$: peripheral vertex, e(v)=diam(G)
• eccentric vertex of u: d(u,v)=e(u)
• boundary vertex of a vertex u: d(u,w)$\leq$d(u,v) for each neighbor w of v
• complete vertex (extrem or simplicial vertex): the subgraph of G induced by the neighbors of v is complete
• $Int(G)$: interior vertex of G if for every vertex u distinct from v, there exists a vertex w such that v lies between u and w
• Theorem: $G = Bound(G) \cup Int(G)$

## Planar Graph

• planar graph: G can be drawed on a plane without edge crossing
• plane graph: G is drawed on a plane with no edge crossing
• regions: connected area divied by plane graph
• exterior regions: a region without bounding
• boundary: subgraph corresponding to a region
• Euler Identity: a planar graph of order n, number of edge m and r regions, n-m+r=2
• Theorem: a planar graph of order $n\geq3$ then $m\leq3n-6$
• maximal planar
• subdivision: one or more vertex of degree 2 are inserted into edge of graph G
• Kuratowski Theorem: G is planar $\iff$ it does not contain a subgraph of $K_5,K_{3,3}$ or subdivision of $K_5, K_{3,3}$
• embedding
• G can be embedded into a plane $\iff$ it can be embedded into a sphere
• $S_K$ surface of genus k: a surface with k handle
• $S_0$: sphere
• $S_1$: torus
• $\gamma(G)$: minimal integer k that G can be embedded into $S_k$
• $A$ and $A'$ are in the same region if there is a line connecting there without crossing edges or vertices of G
• 2-cell: a region in which any closed curves can shrink into a node continuously
• 2-cell embedding: every region is 2-cell embedding
• Theorem: If G is 2-cell embedded into $S_k$ then $n-m+r=2-2k$
• For $n\geq3$, $\gamma(G)\geq\frac{m}{6}-\frac{n}{2}+1$
• $\gamma(K_n)=\lceil\frac{(n-3)(n-4)}{12}\rceil$
• $G'$ is got from $G$ by contracting edge e (or identifying the vertices u,v)
• minor: $H$ can be got be a series of edge contraction from $G$
• Theorem: If $G$ is a subdivision of $H$, then $H$ is a minor of $G$
• Theorem: If $H$ is a minor of $G$, $\gamma(H)\leq\gamma(G)$
• Wagner Theorem: $G$ is planar $\iff$ $K_5,K_{3,3}$ is not a minor of $G$
• minor of graph theorem: For any set of graph $S$, there are two graph in S that one is a minor of the other

## Coloring

• reducible configuration
• unavoidable set of reducible configurations
• dual: a graph corresponding to a map
• coloring (proper coloring): give every vertex a color and the neighboring ones with different colors (The minimal number of independent set G can be divided into; $c:V(G)\rightarrow\mathbb{N}$, when $uv\in E(G)$, $c(u)=\not c(v)$)
• $\chi(G)$: chromatic number, the minimal number of color to color G
• $k$-colorable: $\chi(G)\leq k$
• Four Color Theorem: For every planar graph G, $\chi(G)\leq4$
• color class: the independet set division corresponding to a coloring
• $\chi(G)=1\iff G$ has no edges
• $\chi(G)=2\iff G$ is a nonempty partite graph
• $\chi(C_{2n+1})=3$
• clique: a complete subgraph of graph
• $\omega(G)$: clique number, the largest order of clique in G, $\beta(G)=\omega(\overline G)$
• $\chi(G)\geq\omega(G),\chi(G)\geq\frac{n}{\beta(G)}$
• $\chi(G)\leq 1+\Delta(G)$ (Brook Theorem equal only when G is odd circle or complete graph)
• $\chi(G)\leq 1+\max(\delta(H))$, H is all possible induced subgraph
• Grotzsch graph: triangle-free, $\chi(G)=4$
• edge coloring
• $\chi_1(G)$: edge chromatic number(chromatic index; Divide $G$ into minimum number of 1-regulation graph)
• Vizing Theorem: $\chi_1(G)=\Delta G$ or $=\Delta G+1$
• If $m>\frac{(n-1)\Delta G}{2}$ then $\chi_1(G)=1+\Delta(G)$
• Konig Theorem: For nonempty partite graph, $\chi_1(X)=\Delta(G)$

# Decomposition

• depth-first forest: predecessor subgraph of DFS
• Classification of Edges
• Tree edge: edge in $G_\pi$
• Back edge: ancestor
• Forward edge: descendant
• Cross edge
• Theorem: There is no Forward edges and Cross edge in undirected graphs.
• Parenthesis Theorem
• Nesting of descendant's intervals
• White-path Theorem
• DAG: directed acyclic graph $\iff$ no back edge $\iff$ has topo. ordering
• Toposort: sort vertices in descending order of their finish times
• Connected Component
• Strong Connected Component
• Theorem: Every digraph is a dag of its SCCs
• Kasaraju's Algorithm
• Tarjan's Algorithm
• Semiconnected Digraph
• Toposort+Check edges($v_i,v_{i+1}$)
• Biconnected Graph: contains no cut-nodes
• bicomponenct: a maximal biconnected subgraph

# SSSP & APSP

• Properties of shortest path and relaxation
• Triangle inequality
• Upper-bound property
• No-path property
• Convergence property
• Path-relaxation property
• Predecessor-subgraph property
• Bellman-Ford Algorithm
• Dijkstra Algorithm
• Array: $O(V^2)$
• Min-heap: $O(ElogV)$
• Fib-heap: $O(VlogV+E)$
• DAG-SSSP
• Shortest Simple Path problem: NP
• Difference constraints
• Constraint graph
• Floyed-Warshall Algorithm
• Transitive closure of a directed graph

# Flow

• Flow network: $G=(V,E)$
• Capacity constraint: For all $u,v\in V$, we require $0\leq f(u,v)\leq c(u,v)$
• Flow conservation: For all $u\in V-{s,t}$, $\sum_{v\in V}f(v,u)=\sum_{v\in V}f(u,v)$
• Ford-Fulkerson Method
• net flow: $f(S,T)=\sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in S}\sum_{v\in T}f(v,u)$
• capacity of cut: $c(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v)$
• Max-flow min-cut theorem: The maximum flow is equal to the minimum cut capacity
• Basic Ford-Fulkerson Algorithm: $O(|f^*|E)$
• Edmonds-Karp Algorithm: $O(VE^2)$