1. Basic
   1. Terminologies
      1. adjacent
      2. incident
   2. Complete graph
      1. edge number
   3. subgraphs
      1. clique
      2. independent set
      3. induced subgraph
   4. bipartite
      1. k-cube
   5. path
      1. walk
         1. def: seq. of v and e
            1. (Lemma) every u,v walk contains u,v path
      2. trail
         1. def: no repeated edge
         2. closed
      3. path
         1. def: no repeated vertex
      4. cycle
         1. def: closed trail, length>1, no repeated vertex
         2. (Theorem) Bipartite <=> no odd cycle
   6. degree
      1. regular
      2. degree sum = 2*e(G)
      3. #(odd degree vertex) = even
      4. Theorem and Propositions
         1. [any v, d(v)>k] => [G has a path of length>k]
         2. [any v, d(v)>k; k>2] => [G has a cycle of length>k+1]
         3. two longest path has at least 1 vertex in common
   7. Adjacency matrix
   8. isomorphic
2. connection
   1. connected
      1. def: u,v path exist => u,v connected
      2. def: u connected to every v => G connected
   2. components
      1. def: maximal connected subgraph
   3. cut
      1. deletion increases #(components)
         1. cut vertex
         2. cut edge
      2. Theorem and Propositions
         1. cut edge <=> belongs to no cycle
3. Eulerian
   1. circuit
      1. def: closed trail
   2. def: exist a circuit contains all edge
   3. Theorem and Propositions
      1. Eurlerian <=> degree(all vertex) : even
4. Digraph
   1. edge is ordered pair of vertices
   2. outdegree (d+)
      1. successor
   3. indegree (d-)
      1. predecessor
   4. sum(d+)=sum(d-)=#(e(G))
   5. connection
      1. u,v connected <=> exists u,v path
      2. strongly connected <=> any u,v pair connected
      3. strong components <=> max strong connected subgraph
5. Tree
   1. acyclic
      1. def: no cycle
   2. defs
      1. Tree
         1. connected acyclic graph
         2. connected and (n-1) edges
         3. n-1 edges and acyclic
         4. each pair of vertex connected by unique path
         5. distance: 最短path长度
         6. diameter: 图中最长的distance
         7. eccentricity of v: 图中与v相隔最长的distance
         8. radius: 图中最短的eccentricity
      2. Forest: acyclic graph
      3. leaf: vertex: d(v)=1
      4. spanning tree: spanning subgrah that is a tree
   3. Theorem and Propositions
      1. [n>1] => [>2 leaves]
      2. v is leave => T-v is Tree
      3. every edge in T is cutting edge
      4. adding an edge to T => T has cycle
      5. T and T* is spanning Tree of G => for any e in E(T)-E(T*), there is a e* in E(T*)-E(T) such that T-e+e* is Tree
   4. Counting trees
      1. spanning tree of Kn
         1. t(n) = n^(n-2)
      2. Counting tree <=> sequence
   5. MST
      1. Kruskal's Algorithm
         1. 从E(G)中每次取出最小权的e，加入MST中，s.t. e的加入不能破坏acyclic性
6. Shortest path
   1. Floyd
   2. Dijk
      1. 起始点v, 其他点到u初始距离=无穷，update
7. matching, cover
   1. (max) matching
      1. def: edges w/ no common end points
      2. maximal: 不能扩展
      3. maximum: 没有更大
      4. perfect: 所有点都在matching中
      5. M-alternating: edge交替在M中
      6. M-augmenting: alternating + 起点终点不在M中
      7. Matching maximum <=> no augmenting
      8. G has a matching saturating X <=> |N(S)|>=|S| for all S in X
      9. k regular has perfect matching
   2. (min) cover
      1. vertex cover: 点集, covers all edge
      2. |vertex cover| >= |edge matching|
         1. bipartite => equals
   3. (max) independent set & (min) edge cover
      1. S is vertex cover <=> V(G)-S is independent set
      2. max matching + min edge cover = n(G)
      3. bipartite => max independent set = min edge cover
   4. max独立集 = min点覆盖
   5. max边匹配 = min 边覆盖 (无孤立点)
   6. max 边匹配 = min点覆盖 （二分）
8. connectivity
   1. vertex
      1. vertex cut
         1. def: G-S becomes disconnected
      2. connectivity
         1. Kn => n-1
         2. min vertex cut
      3. k-connected
         1. any k <= connectivtiy
      4. Haray's Graph
         1. n vertex graph with connectivity k, but min # of edge
         2. e(G) = (nk)/2
   2. edge
      1. edge cut
         1. edges connecting [S, ^S]
         2. edge cut is disconnecting set, reverse not true
         3. minimal disconnecting set is edge cut
   3. [G simple] => [connectivity <= edge connectivity <= min degree]
   4. Theorem and Propositions
      1. [n(G) > 3] => [G is 2 connected iff any u,v has 2 disjoint paths]
      2. G is k-connected => (G+y) is k-connected if vertex y adjacent to at least k vertex in G
9. network flow
   1. defs
      1. feasible
      2. tolerance
      3. augmenting path
      4. source sink cut
   2. Max flow min cut
10. Hamiltonian cycle
    1. def: spanning cycle
    2. circumference: G内最长cycle的长度
    3. Hamiltonian => any S in V, G-S has at most |S| components
    4. Hamiltonian <= n(G) >3 && 最小度 > n(G)/2
    5. Hamiltonian <=> G的闭包也是Hamiltonian
       1. 闭包: 连接任意u,v，若d(v)+d(u)>n(G)，重复直到不再存在这样的uv
    6. degree sequence d1<d2<d3..... 对所有i<n/2, 或者di>i或者d(n-i)>(n-i) => Hamiltonian
11. Coloring
    1. defs
       1. coloring
       2. proper
       3. k-colorable
       4. chromatic number
          1. 图的最小着色数
       5. k-critical
          1. 图的最小着色数 且 任何子图都能用更少颜色着色
    2. 着色数<=最大度+1
    3. k-critical => [最小度>=k-1]
    4. Brook: 若非clique也非odd cycle，着色数<=最大度
    5. Turan graph
       1. def: n vertex分为r partite，每个partite的size尽可能一样
       2. Turan graph是所有n vertex r partite中edge最多的
12. Planner Graph
    1. planner <=> 不含K5或者K33 subdivision
    2. 平面图可4着色
    3. 欧拉不变量: V+F-E=2