$G(V,E)$. $|V|=n$, $|E|=m$. $k:$ #components
$C$ cycle, $l$ length of path or cycle.
$B$, set of bridges
$K_n$, complete graph with $n$ nodes
$\chi(G)=j$, chromatic number. $j$-colorable, not $j-1$. called $j$-chromatic
tournament, $K_n$ paint direction.
bi-p. $\Rightarrow$ $\forall C$, $l(C)$ even.
simple, $k$ $\Rightarrow$ $n-k \leq m \leq {n-k+1 \choose 2}$.
simple, $m > {n-1 \choose 2}$ $\Rightarrow$ con.
$\forall v, \text{deg}(v)\geq 2$ $\Rightarrow$ $\exists C$
con. : euler. $\Leftrightarrow$ $\forall v, \text{deg}(v)$ even.
con. : euler. $\Leftrightarrow$ $E$ can split into disjoint cycles.
con. : semi-euler $\Leftrightarrow$ exactly 2 $\text{deg}(v)$ odd
(Ore's) simple, $n\geq 3$, $\forall (u,v)\notin E$, $\text{deg}(u) + \text{deg}(v) \geq n$ $\Rightarrow$ Hami.
(Dirac's) simple, $n\geq 3$, $\forall v, \text{deg}(v) \geq n/2$ $\Rightarrow$ Hami.
tree $\Leftrightarrow$ $\nexists C$, $m=n-1$ $\Leftrightarrow$ con. $m=n-1$ $\Leftrightarrow$ con. $\forall e, e\in B$ $\Leftrightarrow$ $\forall u\neq v$, $\exists$ exactly one path. $\Leftrightarrow$ $\nexists C$, any new edge $|C|=1$
forest, $k$ $\Rightarrow$ $m=n-k$
$T$ is any spanning forest of $G$ $\Rightarrow$ (i) cut $\forall c\in G$, $c \cap E(T) \neq \emptyset$. (ii) $\forall C$, $C\cap E(\overline{T})\neq \emptyset$
(Cayley's) number of labelled trees $|L_n| = n^{n-2}$
number of spanning trees $|S(K_n)| = n^{n-2}$
$K_{3,3}, K_5$ are non-planar.
(Kuratowski's) planar. $\Leftrightarrow$ no sub$(G)$ homeomorphic to $K_{3,3}$ or $K_5$
planar. $\Leftrightarrow$ no sub$(G)$ contractible to $K_{3,3}$ or $K_5$
(Euler) con. planar. $\Rightarrow$ $n-m+f = 2$
polyhedral $\Rightarrow$ $n-m+f = 2$
planar. $\Rightarrow$ $n-m+f = k + 1$
simple, con. planar. $n\geq 3$ $\Rightarrow$ $m \leq 3n-6$. if $G$ no triangles, $m\leq 2n-4$
simple, planar. $\Rightarrow$ $\exists v$, $\text{deg}(v)\leq 5$.
dual $G^*$, con. planar. $\Rightarrow$ $n^*=f, m^*=m, f^*=n$
con. planar. $\Rightarrow$ $G^{**}$ isomorphic to $G$
planar. $G$: $C(G)$ $\Leftrightarrow$ $c(G^*)$.
$c(G)$ $\Leftrightarrow$ $C(G^*)$.
$G^*$ is abstract(dual) $\Rightarrow$ $G$ is abstract dual of $G^*$
planar. $\Leftrightarrow$ $\exists$ abstract
simple, $\max_v \text{deg}(v) = d$ $\Rightarrow$ $d+1$-colorable
(Brooks') simple, con. $G\neq K$, $\max_v \text{deg}(v) = d\geq 3$ $\Rightarrow$ $d$-colorable
(Appel and Haken) simple, planar. $\Rightarrow$ $4$-colorable
map $G$ is $2_f$-colorable $\Leftrightarrow$ euler.
planar. no loop: $G$ $k$-colorable $\Leftrightarrow$ $G^*$ $k_f$-colorable
(Vizing) simple, $\max_v \text{deg}(v) = d$ $\Rightarrow$ $d \leq \chi_e \leq d+1$
$\chi_e(K_n) = n$ odd($\neq 1$), $\chi_e(K_n) = n-1$ even
(Konig's) bi-p. $\max_v \text{deg}(v) = d$ $\Rightarrow$ $\chi_e = d$
$\chi_e (K_{r,s}) = \max(r, s)$
(Hall) $\exists$ complete matching for $V_1$, $G(V_1, V_2)$ $\Leftrightarrow$ for each $k$ girls in $V_1$, collectivly known at least $k$ boys in $V_2$.
max-flow $=$ min-cut
con.: (raw) orientable $\Leftrightarrow$ $\forall e, e\in C$
con.: euler. $\Leftrightarrow$ $\text{indeg}(v)=\text{outdeg}(v), \forall v$
scc. $\forall v, \text{indeg}(v)\geq n/2, \text{outdeg}(v)\geq n/2$ $\Rightarrow$ Hami.
non-Hami. tournament $\Rightarrow$ semi-Hami.
scc. tournament $\Rightarrow$ Hami.
dijkstra. pick min-dist, update its neib.
0-1 bfs. neib. only two kinds dist, so use deque instead of heap.
kruskal. iter edge cost $\uparrow$, dsu maitain connectivity.
lca tarjan offline. dfs. before node end, calc query only when another visited. after visit a node, dsu with its father, update father's ancestor.
bridge. note $u \rightarrow v$, low is minimum of its dfs-after, also mini with begin time when reach a on-track vertex. So $u \rightarrow v$ is bridge iff v's low $>$ u's b.t., aka, those dfs-afters cannot reach back.
cut point. like bridge, but $u$ is c.p. iff v's low $\geq $ u, or $u$ is dfs root with $>1$ children.
toplogical sort. if exists, then by dfs end time. sort
In [ ]: