尝试用英语记。后面有自己翻译一遍的，顺带复习（
Euler tour
An Euler tour is a walk that traverses every edge exactly once and starts and finishes at the same vertex.
Theorem
A connected graph has an Euler tour iff(if and only if) every vertex has even degree.
[!Proof]
Only if:
Assume connected graph $C_1=(V,E)$has an Euler tour.$v_0-…-v_0$.Each time the tour visits a vertex$u$, it enters via one edge and leaves via another, contributing 2 to its degree. So the degree of any vertex $u$ is even.if:
For $C_2=(V,E)$ ，assume deg($v$) is even for all $v\in V$ :
Let $W$: $v_0-v_1-…-v_k$ be the longest walk that traverses no edge more than once. It is common to consider the shortest or longest path.
We want to show:
①: All edges incident to $v_k$are used in$W$: if$v_k-u$is not in$W$,$v_0-v_1-…-v_k-u$ could be a longer path, contradictory.
②: $v_k=v_0$, otherwise$v_k$has odd degree in$W$, according to ①,$v_k$has odd degree in$G$ as well. This is a contradiction. So the original proposition holds.
Suppose $W$is not an Euler tour,$G$is connected, so$\exists$edge is not in$W$but incident to some vertex in$W$. Let $u-v_i$be the edge. Then we start from$u$, walking through$u-v_i-…-v_i$.This is a longer path than$W$. This gives contradiction. So$W$ is an Euler tour.
Directed Graph(digraphs)
Every edge has a direction.
$v_0 -> v_1$, then$v_0$called tail,$v_1$ called head.
indegree : the number of incoming edges
outdegree : the number of outgoing edges
Theorem
Let $G=(V,E)$be an$n$-node graph with $V={v_1,…v_n}$. Let$A={a_{ij}}$denote the adjacency matrix for$G$. That is $a_{i,j} = \begin{cases} 1 & \text{if } v_i \to v_j \text{ is an edge} \ 0 & \text{otherwise} \end{cases}$Let$P_{ij}^{(k)}$denotes the number of walks of length k from$v_i$to$v_j$. Then$A^k={P_{ij}^{(k)}}$ .
[!Proof]
$a_{ij}^{(k)}$denote the$(i,j)$entry in$A^k$ .
Let $P(k)$be the statement that$A^k$correctly counts the walks of length$k$.Base case: $k=1$,Edge$v_i->v_j$:$P_{ij}^{(k)}=1=a_{ij}^{(k)}$, this is true by definition. The case for non-adjacent vertices follows similarly. :
$P_{ij}^{(k)}=0=a_{ij}^{(k)}$.Inductive step: Assume $P(k)$
$P_{ij}^{(k+1)}=\sum\limits_{h:v_h->v_j} P_{ih}^{(k)}=\sum\limits_{h=1}^n P_{ih}^{(k)}\cdot a_{hj} \stackrel{\text{P(k)}}{=} \sum\limits_{h=1}^n a_{ih}^{(k)}\cdot a_{hj}\stackrel{\text{by def}}{=}a_{ij}^{(k+1)}$Def : A digraph$G=(V,E)$is strongly connected if for all$u,v\in V$,$\exists$directed path from$u$to$v$in$G$.
Def : A directed graph is called a directed acyclic graph(DAG) if it does not contain any directed cycles
Tournament graph
A vertex denotes a team. Between $u,v$, either$u$win or$v$ win. So there’s only one directed edge between them.
Def : A directed Hamiltonian path is directed walk that visits every vertex exactly once.
Theorem
Every tournament graph contains a directed Hamiltonian path.
[!Proof]
By induction on $n$.
$P(n) = stating.$Base case: $n=1$ , holds obviously.
Inductive step: Assume $P(k$).
Take out one node $v$. This gives a tournament graph.
By $P(n)$,$v_1->v_2->…->v_n$ is a directed Hamiltonian path.
$Case1$:$v->v_1$ , obviously right.
$Case2$:$v_1 -> v$, let$i$be the smallest number such that$v->v_i$, then$v_{i-1}->v$, so$v_{i-1}->v->v_i$ . Thus, the proposition holds.
A king chicken
Def : Let vertex denote a chicken, if $u$pecks$v$then$u->v$or$u->…->v$ . If a chicken pecks everyone else, then it is a king chicken.
Theorem
A chicken with highest outdegree is a king.
[!Proof]
By contradiction.
Let $u$have highest outdegree. Suppose$u$ is not a king.
$\exists v$,$v->u$and$\forall w, u->w ->v$cannot be true. So if$u->w$then$v->w$. Thus,$outdegree(v) \ge outdegree(u)+1$,that’s a contradiction. So$U$ is a king.
复习 & 手动翻译：
欧拉巡回
欧拉巡回是指遍历每条边恰好一次，并且起点终点相同的途径。
定理
一个连通图有欧拉巡回当且仅当每个顶点的度为偶数。
[!证明]
当：
假设连通图 $C_1=(V,E)$有一条欧拉巡回$v_0-…-v_0$ , 因为每条边只遍历一次，$deg(u)=$ $u$出现在巡回中的次数$\times 2$ 。因而每个顶点的度数都是偶数。仅当：
假设连通图 $C_1=(V,E)$ 的每个顶点度数都是偶数：
设 $W$: $v_0-v_1-…-v_k$是$C_1$ 中最长的，遍历所有边至多一次的途径。图论中常常考虑最长、最短路径。
那么：
①：每条连着 $v_k$的边都在$W$ 中，否则加上那条边显然会构造出一条更长的路径。
②： $v_k=v_0$，否则$v_k$的度数在$W$中为奇数，又因为①，所以其在$G$ 中也是奇数，从而矛盾。
这时，假设 $W$不是欧拉巡回，因为$G$是连通图，存在一条边不在$W$里但连到了$W$中的某个顶点（否则就可以分成两个无关图），假设这条边是$u-v_i$，那么从$u$开始走到$v_i$再走一圈$u-v_i-…-v_i$显然更长，矛盾。从而$W$ 就是一个欧拉巡回。
有向图
每条边都有一个方向。如果 $v_0 -> v_1$那么称$v_0$是尾，$v_1$ 是头。
入度是指指向顶点的边的数量，出度类似。
定理
设 $G=(V,E)$是一个$n$ 个节点的图，$V={v_1,…v_n}$。让矩阵$A={a_{ij}}$ 代表其邻接矩阵，则$a_{i,j} = \begin{cases} 1 & \text{if } v_i \to v_j \text{ is an edge} \ 0 & \text{otherwise} \end{cases}$设$P_{ij}^{(k)}$表示长度为$k$的途径从$v_i$到$v_j$. 那么$A^k={P_{ij}^{(k)}}$ .
[!证明]
$a_{ij}^{(k)}$表示$A^k$ $(i,j)$ 处的元素 .
$P(k)$ 即命题初始状况: $k=1$,如果有$v_i->v_j$:$P_{ij}^{(k)}=1=a_{ij}^{(k)}$, 这根据定义就是对的，没有边也类似 :
$P_{ij}^{(k)}=0=a_{ij}^{(k)}$.归纳步骤：假设 $P(k)$
$P_{ij}^{(k+1)}=\sum\limits_{h:v_h->v_j} P_{ih}^{(k)}=\sum\limits_{h=1}^n P_{ih}^{(k)}\cdot a_{hj} \stackrel{\text{P(k)}}{=} \sum\limits_{h=1}^n a_{ih}^{(k)}\cdot a_{hj}\stackrel{\text{by def}}{=}a_{ij}^{(k+1)}$定义 ： 一个有向图$G=(V,E)$ 是强连通的，如果任意两个点之间都存在一条有向路径。
定义 ： 有向无环图是没有环的有向图（
竞赛图
顶点代表参赛选手/队伍。每对选手只有一个赢，我们用有向箭头表示。即每对顶点之间都有一条有向箭头。
定义 ： 有向哈密顿路径是指一条恰好经过每个顶点一次的有向路径。
定理
每个竞赛图都有有向哈密顿路径。
[!证明]
利用对 $n$ 的归纳法。
$P(n)$ 即命题。初始情况：$n=1$ ，显然成立。
归纳步骤：假设 $P(k)$ 成立。
拿出一个顶点 $v$，这仍然是一个竞赛图，利用归纳假设，可知有 $v_1->v_2->…->v_n$ 这样一条有向哈密顿路径。
① $v$指向$v_1$ ，显然成立。
② 否则，设 $i$是最小的编号，使得$v$指向$v_i$，那么$v_{i-1}->v$，$v_{i-1}->v->v_i$ ，插进去就好了。
综上原命题成立。
鸡王
定义 ： 如果一个顶点代表一只🐔，$u$如果可以啄$v$那么就是说有$u->v$，或者$u->…->v$ 。如果一只鸡可以啄所有其他鸡，那他就是鸡王。
定理
出度最高的鸡是鸡王。
[!证明]
用反证法。
设 $u$ 是出度最高的鸡，假设他不是鸡王。
那么存在 $v$ ，$v->u$而且不存在$u->w->v$，那么如果$u->w$就有$v->w$，这样就说明$v$的出度至少比$u$多$1$，这就矛盾了，所以$u$ 就是鸡王。