初級圖論筆記

Graph：

Terminology of graph：

Graph: $G = (V_G, E_G, f_G)$

  1. $V_G:$ a finite set of elements called vertices.
  2. $E_G:$ a finite set of elementx called edges.
  3. $f_G:$ a function from $EG$ to the 2-multisubsets of $VG$.

Loop: $e \in E_G$ is a loop if $f_G(e)=xx$ for $x \in V_G$.

Simple graph: A graph without any loop and any two edges connected with same two vertices.

Order: $|V_G|$, the number of vertices.

Size: $|E_G|$, the number of edges.

Suppose $e \in GE$ with $fG(e) = xy$. Then the vertices $x, y$ are said to be adjacent, the vertex $x$ is incident with the edge $e$, and the edge $e$ is incident with the vertex $x$.

valency(degree): the number of edges incident with $x$ and another vertex $y \neq x$.

walk: $x_0, e_0, ..., x_i, e_i, ..., e_{n-1}, x_n$ is a walk of length $n - 1$ from $x_0$ to $x_n$ if $f_G(e_i)=x_ix_{i+1} \forall x\in{0, 1, ..., n-1}$.

path: A walk from $x$ to $y$ (resp. $x, y$-path) is a walk without repeated vertices;

trail: A walk from $x$ to $y$ (resp. $x, y$-trail) is a walk without repeated edges;

$G$ is connected if for each pair of distinct vertices $x$ and $y$, there is a walk join $x$ and $y$.

$H$ is a subgraph of the graph $G$ if $H$ is a graph, $VH \subseteq VG$ and $EH \subseteq EG$.

$H$ is an induced subgraph of the graph $G$ if $H$ is the subgraph of $G$ with the maximal possible edges.

$V$ is isolated if $\deg(V) = 0$.

A connected component of $G$ is a maximal (not necessary maximum) connected induced subgraph.

Eulerian trail: A graph is Eulerian if it contains a closed trail using all edges of the graph (Eulerian trail).

有向圖 digraph 的定義：$\vec{G} = (V_\vec{G}, E_\vec{G}, f_\vec{G})$

  1. $V_\vec{G}:$ a finite set of elements called vertices.
  2. $E_\vec{G}:$ a finite set of elementx called edges.
  3. $f_\vec{G}: E_\vec{G} \rightarrow V_\vec{G} \times V_\vec{G}$

Theorem：

  1. A finite graph $G$ has an even number of vertices with odd valency.

    (proof)

    Assume there is no loop in $G$.

    Notices that $\sum_{i\in V_G} deg(i) = 2|E_G|$.

    If $G$ has a odd number of vertices with odd degree, the $\sum_{i\in V_G} \deg(i) = odd \times odd+even\times(even + odd)=odd$.

    Q.E.D

  2. Let G be a graph without isolated vertices. Then G has Eulerian circuit if and only if G is connected and every vertex has even degree.

    (proof)

    先證必要性，再證充分性。

    必要性：

    每此訪問某點都必須要可以被走入又被走出，所以每個點的度數都必然是偶數個。

    充分性：

    在沒有 isolated vertices 的情況，每個節點 valency 都是偶數，則圖 $G$ 至少有 $|VG|$ 條邊，而一張圖在沒有環的情況，至多只有 $|VG| - 1$ 條邊，所以圖 $G$ 必定存在環。

    令此環上的邊叫做 $C_1$，顯然圖 $G$ 的子圖 $G_1 = G-C_1$，當中每一個節點也擁有even degree，因為一個環上的點必定存在偶數條邊。

    子圖 $G_2$ 可能有多個 component，且每個 component 的 vertices 也全為even degree，所以也必定存在環，再且每個 component 都必定和 $C_i$ 有共用 vertex。依次反覆，可以發現最後每個component都是環。

    兩個環如果有共同節點，則他們可以被合併成一個環。

    所以最後可以得知，原圖會形成一個環。

Tree：

Definition of Tree

A tree $G$ is equivalent:

  1. $G$ is connected and no cycles.
  2. $G$ is connected and has n - 1 edges.
  3. $G$ has n - 1 edges and no cycles.
  4. $G$ has no loops and has, for each $u, v \in VG$, exactly one $u, v-path$.

proof: 這四個是等價的。

  1. $\Rightarrow$ 2.

    一開始的 $G$ 共有 $|VG|$ 個點，假設我們一條邊一條邊的加入，則一開始有 $0$ 條邊，和 $|VG|$ 個 component。

    每加入一條邊，最多能使得兩個 component 合併。所以最少需要 $|VG| - 1$ 次的加邊，才能使得整個 $G$ connected。

    有了 $|VG| - 1$ 條邊的 $G$ 已經 connected，所以對於任意 vertices pair $(i, j)$，本來就已經有存在一條 $i, j-path$，所以加入再加入邊 $ij$，則會產生環。

    所以我們知道，對於一個無環的 connected graph，必然有且僅有 $n - 1$ 條邊。

  2. $\Rightarrow$ 3.

    對於一個沒有 cycle 的圖，產生 cycle 的條件便是，再加入一條邊，連接兩個本來就在同一個 connected component 的 vertices。

    所以假設當 $G$ 的 order $= n$，且 $n = i$ 的時候，$G$ 是一個 connected 且僅有 $i - 1$ 條邊的圖。

    則當 $n = i + 1$時，新增入了一個 vertex，新圖 $G'$ 形成兩個 component，分別是原圖$G$ 和新點。

    此時因為要保持 connected，所以必然加入一條邊連接 $G'$ 和新點，這個過程是不會產生 cycle 的。

    最後，當 $n = 1$的時候，很明顯只有 1 個 vertex 和 0 條邊，並不會存在 cycle。

  3. $\Rightarrow$ 4.

    很顯然不存在 cycle 則也不會有 loop。 CLEAR。

  4. $\Rightarrow$ 1.

    for each $u, v \in VG$, exactly one $u, v-path$.

    代表對於任意相異 $u, v$，都有且僅有一條 path，所以必定不存在 cycle；對相同的 $u, u$ 也不存在 loop，所以亦不存在 cycle。且此圖是 connected 的。

Prufer Codes

Prufer codes are sequences over $[n] := {1,2,...,n} $ of length $n - 2$ that associated to trees T with $VT = [n]$

Prufer codes:

  1. Remove the leaf $L$ with the least index.
  2. Add the index of the parent of $L$ into the sequence.
  3. Repeat until the graph has two vertices.

Easily construct a tree from any prufer code

Theorem: Prufer code and tree is one to one mapping

$\rightarrow$ The number of different prufer codes is also that of different trees.

Minimum Spanning Tree

spanning tree: A spanning tree of graph $G$ is subgraph $T$ of $G$ such that $T$ is a tree and $V_T = V_G$.

A weighted graph is a graph $G$ together with a function $c : EG → R$, called the cost function.

For a spanning tree $T$ of weighted graph $G$ with cost function $c$, the cost of $T$ is defined as: $$ c(T) = \sum_{i\in{ET}} c(e)$$

Kruskal’s Algotithm: A greedy algorithm ifind a spanning tree with minimum cost.

  1. E = $∅$;
  2. Do while there is $e ∈ EG − E$ such that $E ∪ {e\ }$ contains no cycle,
    1. pick such $e$ with $c(e)$ minimum;
    2. $E := E ∪ {e}$.
  3. Output the graph $T_0$ with $V_{T_0}$ = $V_G$ and $E_{T_0}$ = E.

(Proof. )

First, $T$ is a spanning tree. This is because:

Second, $T$ is a spanning tree of minimum weight. We will prove this using induction. Let $T^∗$ be a minimum-weight spanning tree.

$T = T^∗$, then $T$ is a minimum weight spanning tree. If $T \neq T^∗$, then there exists an edge $e ∈ T^∗$ of minimum weight that is not in $T$. Further, $T ∪ e$ contains a cycle $C$ such that:

Consider the tree $T_2 = (T - {f}) \cup {e}$:

We can redo the same process with $T_2$ to find a spanning tree $T_3$ with more edges in common with $T^∗$. By induction, we can continue this process until we reach $T^∗$, from which we see $$c(T) ≤ c(T_2) ≤ c(T_3) ≤···≤ C(T^∗)$$

Since $T^∗$ is a minimum weight spanning tree, then these inequalities must be equalities and we conclude that $T$ is a MST.

BFS tree

A subgraph T of G is a BFS tree rooted at $p_0$ iff $p_o \in T$ and $\forall p\in V_T, \partial_T(p_0,p)=\partial_G(p_0,p).$

DFS tree

Remark.

One of $x, y$ in a DFS tree is the descendent of the other if and only if $x, y$ are not in different branches of a vertex.

Claim. (#2.3)

Let $G$ be a connected graph with a vertex $p_0$. Let $T$ be a DFS spanning tree of $G$ rooted at $p_0$. Then there is no edge between two vertices in different branches of a vertex.

Bridge

Bridges are those edges whose deletion results in the graph disconnected.

Claim. (#2.4)

Let $G$ be a connected graph with a vertex $p_0$. Let T be a DFS spanning tree of $G$ rooted at $p_0$, and $xy$ be an edge of $T$ which is not a bridge in $G$. If $x$ is the parent of $y$ then there is an edge between some descendent of y and some ancestor of $x$.

(Proof.)

Deleting the edge $e = xy$ results two components in $T − e$, which are connected by another edge $ab$ in $G$ since $e$ is not a bridge. And $ab$ can not be in different branches(by #2.3). Hence one is a descendent of y and the other is an ancestor of x.

Terminology

An orientation of a graph $G$ is a digraph obtained from $G$ by assigning a direction to each edge of $G$.

A digraph $\vec{G}$ is strongly connected if for any two vertices $x, y − \vec{G}$ there exists an $x, y-$directed walk.

$\tau(G)$ is the number of spanning trees on $G$, for any edge $e$ in G,$\tau(G)=\tau(G - e) + \tau(G/e)$.

Adjacency matrix A is a matrix indexed by vertices such that $A_{xy} = $ the number of edges connected $x$ and $y$.

Laplace matrix: Let D denote a diagonal matrix with rows and columns indexed by vertices of $G$ such that $Dxx = $degree of $x$. Then Laplace matrix of $G$ is $D - A$.

Let $M(i|i)$ is the principle submatrix of $M$ obtained by deleting the row and column indexed by $i$.

The number of trees with vertex set $[n]$ is equal to the number of spanning trees of $K_n$.

$K_n$ is a completed graph with its order $n$. $K_{m, n}$ is a bipartie graph with the size of one color m, and the size of the other n.

$C_n$ is a cycle which length is n.

Theorem

Let $G$ be finite connected graph without bridges. Then $G$ has a strongly connected orientation.

(Proof.)

  1. Fix a point $p_0$ in $G$ and find a DFS spanning tree T rooted at $p_0$.
  2. Give directions of edges in $T$ that causes all directed paths from the. root $p_0$ to leafs.
  3. For the two endpoints of an edges not in $T$, one must be descendent and the other ancestor by Proposition # 2.4, and we give the direction from descendent to ancestor.
  4. Since $G$ has no bridge, one can argue that there is a directed back and forth path from each leaf back to root $p_0$.
  5. For two vertices x, y, there is a directed x, y-path by connecting three paths: from x to one of its descendent leaf a, a bach and forth path from a to root p0, and a path from p0 to y.

Matrix-tree theorem

$$\tau(G) = \det(L(G)(u|u)), \text{ for any } u \in VG$$

(lemma.)

Let $e$ be an edge in $G$ with one end $i$. Then $$\det(L(G)(i|i)) = \det(L(G-e)(i|i)) + \det(L(G/e)(i|i))$$

Suppose $e = 12$, $i = 1$, and $d_i$ is the degree of vertex $i$. Then

$$\begin{equation} \begin{split} \det(L(G)(1|1)) & = \begin{pmatrix}d_2 & \ldots \ \vdots & d_3\\end{pmatrix} \ & = \begin{pmatrix}d_2 - 1 & \ldots \ \vdots & d_3\\end{pmatrix} & + & \begin{pmatrix} 1 & \ldots \ 0 & d_3 \ \vdots \\end{pmatrix} \ & = \det(L(G - e)(1|1)) & +& \det(L(G / e)(1|1))& \end{split} \end{equation}$$

(proof.)

Since $τ (G)$ and $det(L(G)(u|u))$ satisfy the same pattern of recurrence relation, we only need to check the initial conditions. The initial condition is $c$ vertices with no edge.

If $c > 1$ then $$τ (cK1) = 0 = detL(cK1)(u|u),$$

If $c = 1$ then $$τ (K1) = 1,$$ but $det(L(K1)(u|u))$ does not make sense. For convenience sake, we can define $det(\phi) = 1$.

Or we could choose the initial conditions to be $m$ copies $G_m$ of multi-edges, and use $τ(G_m) = m = det[m]$ .

Cayley formula

$$\tau(K_n) = n ^ {(n - 2)}$$

(proof.)

第一次作業：

題目：

    • Show that every tree T of order n ≥ 2 has at least two leaves.
    • Prove that every simple graph with at least two vertices has at least two vertices of equal degree.
    • Construct the tree on [9] corresponding to the Prűfer code (1,1,3,4,4,4,9).
    • A trail in G is Eulerian if it is a trail using all edges of G. Show that a connected graph with exactly two vertices of odd degrees has an Eulerian trail.
    • Let [7] := {1,2,...,7}.
      • How many trees on vertex set [7]?
      • If i ∈ [7] appears d times in the Prűfer code P(T) of a tree T on vertex set [7], what is the degree of i in T?
      • How many trees on [7] with deg(2) = deg(3) = 3 and deg(5) = 2?

  3. Show that a nonnegative integer sequence $d_1 ≥ d_2 ≥ ··· ≥ d_n$ is a degree sequence of a loopless graph (multiple edges allowed) iff $\sum^n_{i=1}d_i$ is even and $d_i \leq \sum^n_{i=2}{d_i}$.

  4. Let $d_1 ≤ ··· ≤ d_n$ be the vertex degrees of a simple graph $G$. Prove that G is connected if $dj ≥ j$ when $j ≤ n−1−d_n$.

    (Hint: Consider a component that omits some vertex of maximum degree.)

解答：

    • Show that every tree T of order n ≥ 2 has at least two leaves.

    對於一顆 order 為 n 的樹 T，我們可以知道他存在 n - 1 條邊。

    即 $\sum_{i\in VT} \deg(i) = 2n - 2$，根據鴿籠原理 n 個點有 2n - 2個 degree，至少有 2 個 vertices 他們的平均 degree 數小於 2。

    且因為這是一顆樹，沒有 isolated vertex，所以對於任意的一個 vertex $x$，$\deg(x) \geq 1$始終成立，故存在至少兩個 vertices 他們的 degree 數為 1。

    • Prove that every simple graph with at least two vertices has at least two vertices of equal degree.

    假設simple graph $G$ 的 order 為 $n$，且每一個點都有相異的 degree，則假設分別為 $a_1, a_2 , ... , a_n$，且 $\forall x\neq y$，都有 $a_x\neq a_y$，且由於總共只有 $n$ 個 vertice，最大 degree 不超過 n - 1，所以此時 $\cup_{x\in VG} \deg(x)={0, 1,..., n - 1}$

    但 degree 為 n - 1 的點必定不能與 degree 為 0的點共存在一個 $|VG| = n$ 的圖（一個連接所有點，一個點與所有點都不連接，矛盾），所以得證此圖不存在。

    • Construct the tree on [9] corresponding to the Prűfer code (1,1,3,4,4,4,9).

    • A trail in G is Eulerian if it is a trail using all edges of G. Show that a connected graph with exactly two vertices of odd degrees has an Eulerian trail.

    假設原圖 $G$ 兩個奇數度數點分別為 $x, y$，則加一條邊 $xy$，成圖 $G'$。此時每個點都是 even degree，所以此圖會構成一個 Eulerian circuit。

    對於一個環 $C$，在 $C$ 當中刪除一條 $xy$ 的邊，則 $C - xy$ 會成為一個 $x, y$ 的 trail。

    所以當圖 $G'$ 刪除 $xy$ 的時候，會變成一個 $x,y -$ trail，且這個 trail 是個 Eulerian trail。

    • Let [7] := {1,2,...,7}.

      • How many trees on vertex set [7]?

      由 Cayley's formula，可知有 $5 ^ 7$ 種可能。

      • If i ∈ [7] appears d times in the Prűfer code P(T) of a tree T on vertex set [7], what is the degree of i in T?

      出現 d 次，代表與 vertex $i$ 的 $d$ 個節點都陸續被刪除。

      且如果 vertex $i$ 被刪除了，則代表他還與另一個 vertex 相鄰，所以 degree 為 $d + 1$；如果 vertex $i$ 沒有被刪除，代表最後留下了這個點和另一個點，所以 degree 也為 $d + 1$。

      • How many trees on [7] with deg(2) = deg(3) = 3 and deg(5) = 2?

      該樹可以對應到 prufer code 為 [2, 2, 3, 3, 5]，所以只有 $1$ 種可能。

  3. Show that a nonnegative integer sequence $d_1 ≥ d_2 ≥ ··· ≥ d_n$ is a degree sequence of a loopless graph (multiple edges allowed) iff $\sum^n_{i=1}d_i$ is even and $d_1 \leq \sum^n_{i=2}{d_i}$.

    必要性：

    （一）如果一張圖 $G$ 沒有 loop，則存在 $\sum^n_{i\in VG} \deg{(i)}=2|EG|$，所以 $\sum^n_{i\in VG} \deg{(i)}$ 必然是偶數。

    （二）一個 vertex 的 degree 倘若增加了 1，那麼必然與之對應的另一個 vertex 也會增加 1。所以倘若我們一條邊一條邊的加入到圖中，以此來計算 degree，可以得知沒有任何一個 vertex 的 degree 會超過總 degree 數的一半。

    充分性：

    首先假設 $\sum_{i=2}^n d_i=d_1$，則顯然可以構造出一張圖。

    每個 $i \geq 2$ 的 vertex $i$ 都和 $d_1$ 對應到的 vertex 連 $d_i$ 條邊，則構造出了所求的圖。

    再假設 $\sum_{i=2}^n d_i>d_1$，且因 $\sum_{i=1}^n d_i$ 是偶數，所以可以知道 $(\sum_{i=2}^n d_i) - 2\geq d_1$。

    假設 $v \leq n$，$d_v >0$ 且 $\forall n\geq v>u,d_v=0$。我們此時可以將 ${d_1,d_2,...,d_{v-1} - 1,d{v} - 1, ...,d_n}$ 所對應之圖加上一條邊，連接 $d_{v-1} - 1,d{v} - 1$ 所對應到的 vertices，此時就可以由 ${d_1,d_2,...,d_{v-1} - 1,d{v} - 1, ...,d_n}$的圖構造出滿足 ${d_1,d_2,...,d_n}$的圖。

    假設 $(\sum_{i=2}^n d_i) - 2k = d_1$，其中 $k \in \mathbb{N}$，則依照以上步驟重複 k 次，得到的 degree sequence $<d'i>$，就可以滿足 $\sum{i=2}^n d'_i=d'_1$，所以可以由數學歸納法，得證原圖存在。

  4. Let $d_1 ≤ ··· ≤ d_n$ be the vertex degrees of a simple graph $G$. Prove that G is connected if $d_j ≥ j$ when $j ≤ n−1−d_n$.

    (Hint: Consider a component that omits some vertex of maximum degree.)

    假設${d_1,d_2,...,d_n}$所對應到的圖 $G$ 存在兩個以上的 connected component，則至少有一n個 component 包含 degree $=d_n$的 vertex，所以這個 component 要包含至少 $d_n + 1$ 個 vertices。

    則剩餘的其他 component 的 vertices 數必然小於等於 $n - d_n - 1$，假設其中某個 component 的 vertices 數為 $t$，且 $t \leq n - d_n - 1$，可以知道當中最大的 degree 數不超過 $t - 1$，而這個 component 當中 degree 最大的 vertex 之 degree 必然大於等於 $d_t$，所以可以得知 $d_t \leq t - 1$，與 $d_j ≥ j$ when $j ≤ n−1−d_n$ 相矛盾。

The distance $\partial_G(x, y)$ of two vertices $x, y$ in $G$ is the small length of $x, y-$walk.

Coloring

Coloring

  1. A $k$-coloring of $G$ is a function $f : V(G) → S$ for some set $S$ with cardinality $|S| = k$.
  2. The elements of $S$ are called colors
  3. A $k$-coloring f is proper if $f(u) \neq f(v)$ for $uv ∈ EG$.
  4. G is $k$-colorable if it has a proper $k$-coloring.
  5. The chromatic number $χ(G)$ is the least $k$ such that $G$ is $k$-colorable.

Example

$\chi(K_n) = n$ $\chi(K_{m, n}) = 2$ $\chi(C_n) = \begin{cases} 2,& \text{if n is even}\ 3,& \text{if n is odd} \end{cases}$ $\chi(P_n) = \begin{cases} 1,& \text{if } n = 1\ 2,& \text{if } n \geq 2 \end{cases}$

Clique and clique number

A clique in $G$ is a complete subgraph in $G$. The clique number $\omega(G)$ is the maximum size of a clique in $G$.

Coclique and independent number

A coclique(independent set) is a set of vertices with each pair of vertices not adjacent.

The independent number $\alpha(G)$ of $G$ is the maximum size of a coclique in G.

Theorem

  1. $\chi(H) \leq \chi(G)$, for any subgraph $H$ of $G$.

  2. $\chi(G) \geq \omega(G) \text{ and } \chi(G) \geq \frac{|VG|}{\alpha(G)}$

    (proof.) The first bound follows since there exists a clique of size $ω(G)$, that must use $ω$ different colors. The second bound follows since in a coloring, the vertices in the same color forms a coclique, which has order at most $α(G)$.

  3. Let $G$ be a simple graph with degree sequence $d_1 ≥ d_2 ≥ \cdots ≥ d_n$, then$\chi(G) \leq 1 + \max_{}{{\min(d_i, i-1)} \leq 1 + d_1}$.

    (proof.)We use $k := 1 + \max{min(d_i, i - 1)}$ colors to color $VG = {1, 2, \cdots , n}$ listed according to the degree sequence. First we color 1 by any color. Suppose we have colored $1, 2, \cdots, i-1$. Since $k > min(d_i , i − 1)$, we can choose a color for i which is different from those colors of its neighbors in $1, 2, \cdots , i − 1$. This defines a proper coloring on $G$.

  4. Suppose G is a connected graph with order n and $G \neq K_n$ or $G \neq C_n \text{ and n is odd}$. Then $\chi(x) \leq \Delta(G)$. $\Delta(G) = \max{d_i}$ where $d_i$ is the degree of vertex $i$.

k-Critical Graphs

A graph $G$ is $k$-critical if $χ(G) = k$ and $χ(H) < k$ for any proper subgraph $H$ of $G$.

Every graph $G$ contains a $χ(G)$-critical subgraph.

Suppose G is $χ(G)$-critical. Then $δ(G) ≥ χ(G) − 1$, where $\delta(G)$ is the minimum degree of the vertices.

(proof.) Suppose there exists $x ∈ V(G)$ with degree $χ(G) − 2$. Using this and by $χ(G − x) ≤ χ(G) − 1$, we can color x differently to its neighbors by one of the $χ(G) − 1$ colors using in a coloring of $G − x$.

Szekeres-Wilf Theorem: $$χ(G) ≤ 1 + \max_{H⊆G}{δ(H)}$$

第二次作業

    • Let $K_n$ have vertex set $[n]$ and edges $ij$ with cost $i + j$. What is the minimum cost of a spanning tree of $K_n$? Explain your answer. $$\text{Ans} = (\sum_{i\in[n]}i + 1) - 1=\frac{(n+2)(n-1)}2-1$$ Applying Kruskal’s algorithm , the output edges are $12, 13, \cdots 1n$. We show this by induction in steps. Suppose the output is $12, 13, \cdots 1j$ on step $j$. For an edge $ab\neq 1{j+1}$ with cost $a+b$ at most $j + 2$ we must have $a,b ≤ j$, making a cycle with the edges $12, 13, \cdots 1 j$. This proves the $1{j +1} is the only choice at step $j +1$.

    • Find a strongly connected orientation of $K_n$.
      Let $VKn = [n]$ and defined directed edge set as $${\vec{i j} \text{ | } i \text{, } j \in [n], j = i+1 \text{ or } j < i−1}$$

    • Determine $τ(K_{3,3})$. 考慮他的 laplacian matrix:

    $$L=\begin{bmatrix} 3 & 0 & 0 & {-1} &{-1}&{-1} \ 0 & 3 & 0 & {-1} &{-1}&{-1} \ 0 & 0 & 3 & {-1} &{-1}&{-1} \ {-1} &{-1}&{-1} & 3 & 0 & 0 \ {-1} &{-1}&{-1} & 0 & 3 & 0 \ {-1} &{-1}&{-1} & 0 & 0 & 3 \end{bmatrix}$$

    所以答案就是：

    $$\begin{vmatrix} 3 & 0 & 0 & {-1} &{-1} \ 0 & 3 & 0 & {-1} &{-1} \ 0 & 0 & 3 & {-1} &{-1} \ {-1} &{-1}&{-1} & 3 & 0\ {-1} &{-1}&{-1} & 0 & 3 \end{vmatrix} = 81$$

    • Let $G$ be a graph such that $χ(G − x − y) = χ(G) − 2$ for all pairs $x, y$ of distinct vertices. Prove that G is a complete graph.
      假設 $G$ 並不是 complete，則我們取 $x, y$ 為 nonadjacent 的兩個 vertices，且我們可以用 $\chi(G) - 2$ 種顏色給 $G$ 著色，再用一種額外的顏色給 $x, y$ 著色，則可使$\chi(G) = \chi(G) - 1$，引發矛盾。

  2. Let G be a connected weighted graph of order $n$ with cost function $c$, $a,b ∈ V$ G and $ab ∈ EG$. Consider the Prim’s Algorithm:

    1. V = ${a}$,E = $\phi$;
    2. Do while there is $x ∈ V$ and $y ∈ V_G−V$ such that $xy\notin E_G-E,$
      • pick such $e = xy$ with $c(e)$ minimum;
      • $V = V ∪ {y}$ and $E := E ∪ {e}$.
    3. Output the graph $T_0$ with $VT_0 = V$ and $ET_0 = E$. Show that $c(T_0) ≤ c(T)$ for any spanning trees $T$ of $G$.

假設以此步驟產生出來 spanning tree 為 $T_0$，我們將 $ET_0$ 按照邊權遞增順序寫成 ${e_1, e_2, ..., e_{i-1}, e_i, ..., e_{n-1}}$，且和 $ET_0$ 擁有最長相同邊權前綴的最小生成樹為 $T^。假設 $T_0 = T^$，則證明完畢。再假設 $T_0 \neq T^$，我們從中選取一條最小的邊 $e_i \in T^$ 且 $e_i \notin T_0$，則我們將此邊加入 $T_0$，即 $T := T_0 + e_i$，則顯然會產生一個環 $c$，將此環 $c$ 的最小的一個邊假設叫做 $f$，且 $f \notin T_$，則根據 Prim 算法的選擇策略，$c(f) \leq c(e_i)$。
假設 $c(f) < c(e_i)$，則我們可以將 $T^ := T^* - e_i + f$，這仍然是 spanning tree 且擁有更小的 weight，與 $T^$ 為最小生成樹的假設不符。
假設 $c(f) = c(e_i)$，則我們可以將 $T^{\prime} := T^* - {e_i} + {f$}，這保證了 $c(T^{\prime}) = c(T^{})$，但由於原本的 $T_0$ 和 $T^$ 邊權前綴為 ${e_1, e_2, ... , e_{i-1}}$，而 $T_0$ 和 $T^{\prime}$ 之邊權前綴為 ${e_1, e_2, ... , e_{i-1}, e_i}$，這與 $T^$ 與 $T_0$ 擁有最長相同前綴的假設矛盾。
因此得證 $T_0 = T^$，且因為 $T^*$ 是最小生成樹，所以由 Prim 演算法所產生的 $T_0$ 也是最小生成樹。

  1. Use Cayley’s Formula to prove that the graph obtained from $K_n$ by deleting an edge has $(n−2)n^{ n−3}$ spanning trees. (Hint. $τ(K_n/e)$ is independent of $e$). $$\begin{equation} \begin{split} \det(L(G)(1|1)) & = \begin{pmatrix}d_2 & \ldots \ \vdots & d_3\\end{pmatrix} \ & = \begin{pmatrix}d_2 - 1 & \ldots \ \vdots & d_3\\end{pmatrix} & + & \begin{pmatrix} 1 & \ldots \ \vdots & d_3\\end{pmatrix} \ & = \det(L(G - e)(1|1)) & +& \det(L(G / e)(1|1))& \end{split} \end{equation}$$ 考慮 $(^n_2)\tau(K_n/e) = \tau(K_n)(n-1) = n^{n-2}(n-1)$，所以 $\tau(K_n/e) = 2n^{n-3}$。 $\tau(K_n-e) = det(L(K_n-e)(1|1) = det(L(G)(1|1)) - det(L(K_{n-1})(1|1)) = n^{n-2} - 2n^{n-3}$
  2. Determine $τ(K_{2,m})$.
    (Solution 1)
    Note that every spanning tree of $K_{2,m}$ has a unique vertex in the $m$-vertex part with degree 2. Hence $$τ(K_{2,m}) = (^m_1)\cdot 2^{m-1}$$ (Solution 2)
    $τ(K_{2,m} −e) =τ(K_{2,m−1}) = 2^{m−2}(m−1)$ —— (a)

Extremal Graph

Example:

  1. If $G$ is connected with order $n$ then $|EG| ≥ n − 1$ and tree is the unique extremal graph of this inequality, i.e. equality holds iff $G$ is a tree.

  2. If G is a simple graph without cycle and with order n then |EG| ≤ n − 1 and tree is the unique extremal graph of this inequality, i.e. equality holds iff G is a tree.

Proposition(Mantel Theorem): A simple triangle-free graph $G$ of order $n$ has at most $\lfloor{\frac{n^2}4}\rfloor$ edges.

(proof.) Consider the extremal graph $K_{\lfloor\frac{n}2\rfloor, \lceil\frac{n}2\rceil}$, it has maximum number of edges $\lfloor\frac{n}2\rfloor \times \lceil\frac{n}2\rceil$ = $\lfloor{\frac{n^2}4}\rfloor$.

  1. Induction on $n = |V_G|$.
  2. Pick an edge $xy$ of $G$.
  3. Then the number of edges in $G - {x, y]}$ is at most $\lfloor{\frac{(n-2)^2}4}\rfloor$.
  4. Since each vertex can adjacent to at most one of ${x, y}$.

$$|EG| \leq \lfloor\frac{(n-2)^2}{4}\rfloor + (n-2) + 1 = \lfloor \frac{n^2}4\rfloor$$

Turán Theorem

A simple $K_p$-free graph $G$ of order $n$ has at most $M(n, p)$ edges, where $M(n, p)$ is the number of edges in the complete multipartite graph of order $n$ with $p − 1$ almost equal parts(MAX - MIN $\leq 1$).

(proof.)

We prove by induction on $n$,

Basis: This is true for $n ≤ p − 1$ with $G$ a subgraph of $K_n$ and $M(n, p) = (^n_2)$.

We might assume G is Kp-free with maximal edges. Then G contains $K_{p−1}$, and each of the remaining $n − (p − 1)$ vertices is adjacent to at most $p − 2$ vertices of $K_{p−1}$.

Induction step: By induction hypothesis the subgraph induced on the remaining $n − (p − 1)$ vertices is at most $M(n − (p − 1), p)$ edges. Then the number of edges in G is at most $$M(n − p + 1, p) + (n − p + 1)(p − 2) + (^{p − 1}_2)=M(n, p).$$

Girth

The girth of a graph is $G$ the size of a smallest cycle in $G$. If there is no cycle, then the girth is infinity.

Remark.

G has girth at least 3 iff $G$ is simple. G has girth at least 4 iff $G$ is simple and triangle-free. G has girth at least 5 iff $G$ is simple, triangle-free and square-free. If G has girth at least 4, then the Mantel Theorem says that $|EG| \leq \lfloor \frac{|VG|^2}4\rfloor$.

Theorem 4.2

If $G$ has girth at least 5, then $|EG| \leq \frac{|VG|\sqrt{|VG| - 1}}{2}$.

(proof.)

$$|VG|(|VG| - 1) = \sum_{x\in VG}(|VG| - 1) \ \geq \sum_{x\in VG}|G_1(x)\cup G_2(x)| =^1 \sum_{x\in VG}{\sum_{y\in G_1(x)}{\deg(y)}} =^2 \sum_{x\in VG}\deg(y)^2 \ \geq^3 \frac{1}{|VG|}(\sum_{y \in VG} \deg(y))^2 = \frac{1}{|VG|}(2|EG|)^2$$

  1. 用到 girth $\geq 5$ 的性質，所以每一個 $G_1(x) - {x}$ 都是互斥的。
  2. Each $\deg (y)$ is summed $\deg(y)$ times from the neighbors $x$ of $y$.
  3. By Cauchy–Schwarz inequality.

The inequalities holds when both the first and second inequalities holds.

  1. $\text{diameter}(G) \leq 2$.
  2. Each vertex has same degree, i. e. $G$ is regular.

第三次作業

    • Let $a,b, c,d ∈ [9]$ be distinct, $G = (V,E)$ be a graph, with $V = {1,2,...,10000}$ and $E = {xy | x−y ∈ {±a,±b,±c,±d}}$.

      1. Show $∆(G) = 8$.
        Proof. This is clear from the construction of $G$。
      2. Show $χ(G) ≤ 5$.
        Proof.
        (Method1) Note that each vertex $i$ has at most 4 neighbors $j$ with $j < i$, so we can pick a color not used in these four neighbors.
        (Method2) By Szekeres-Wilf theorem, we have $$χ(G) ≤ 1+\max_{H⊆G}δ(H).$$ Note that by considering the degree of the least labeled vertex in $VH$, any induced subgraph $H$ of $G$ has minimum degree at most 4. Hence $χ(G) ≤ 1+4 = 5$.

    • Show that a simple triangle-free graph $G$ on $n ≥ 2$ vertices with $⌊\frac{n^2}4⌋$ edges is $K_{⌊n/2⌋,⌈n/2⌉}$.
      Wrong Solution:

    We show that G is bipartite first. If G has girth at least 5 then by Theorem 4.2, $|EG| ≤ \frac{n \sqrt n}2$, so $|EG| \neq ⌊\frac{n^2}4⌋$, a contradiction. Hence $G$ is triangle-fee with girth at most 4. This implies $G$ being bipartite. Note that a bipartite with bipartition of sizes $a, n−a$ has at most a(n−a) edges, and the maximum of $a(n−a)$ is when $a = ⌊n/2⌋$ and the extremal graph is $K_{⌊n/2⌋,⌈n/2⌉}$.

    Consider $C_4, C_5$ with one common vertex.

    • A vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge. A matching is a set of edges without common endpoints. Find all matchings $M$ and all vertex covers $C$ of size 4 in the following graph. $$C = {F_1, F_2, M_2, M_3} \ M = {F1M1,F2M4,F3M2,F4M3}$$
    • Let $G$ be a simple graph with 10 vertices and 26 edges. Show that $G$ has at least $5$ triangles. (Hint: $\frac{1}3 ∑_{xy∈EG }|G_1(x)∩G_1(y)|$ is the number of triangles.

    (general case.)A simple graph order $n ≥ 3$ with at least $⌊\frac{n^2}4⌋ + 1$ edges contains at least $⌊n/2⌋$ triangle.

    By induction on n.

    Basis: A graph order $n = 3$ with $3$ edges is $K_3$, there is one triangle. That order $n = 4$ with 5 edges is $K_4$.

    Induction step:

    If each edge is in a triangle then the number T of triangles of $G$ is $$T = \lceil \frac{|EG|}3 \rceil \geq \lceil (⌊\frac{n^2}4⌋ + 1)/3\rceil \geq ⌊\frac{n}2⌋.$$

    Otherwise, assume $xy$ is an edge not contained in any triangle and on contrary, $T \leq ⌊\frac{n}2⌋ - 1$. Then $|G_1(x) + G_1(y)| \leq n - 2$ and $|E(G - {x,y})| \leq ⌊\frac{(n-2)^2}4⌋$

    • Find a simple graph $G$ of order 10 and size 26 with exactly 5 triangles.

    (Solution.) The graph $K_{5,5} + e$ is such a graph, where $e$ is a new edge connecting two vertices in the same part of the bipartition of $K_{5,5}$.

  3. Let $G$ be a graph such that every two odd cycles in $G$ have a common vertex. Prove that $χ(G) ≤ 5$.

(proof.) If G has no odd cycle then G is bipartite and $χ(G) ≤ 2$. Pick an odd induced cycle $C$. Then $G−VC$ has no odd cycle by the assumption(every two odd cycles in $G$ have a common vertex, so if we remove one cycle, it will destroy all the cycles). Hence $G−VC$ is bipartite and can be colored by 2 colors. Color $VC$ by three new colors and we have a proper 5-coloring of $G$.

  1. A graph is $k$-regular if every vertex has degree $k$, where $k ≥ 1$. Let $G$ be a $k$-regular bipartite graph with bipartition .
    • Show that $|X| = |Y|$..
      (proof.) Counting the pair $(x, e)$ in two ways such that $x ∈ X, e ∈ EG$ and $x$ is incident with $e$, we have $|X|k = |EG|$. Similar $|Y|k = |EG|$. Hence $|X| = |Y|$
    • Show that $G$ has a complete matching from $X$ from $Y$..
      (proof.) For any $S ⊆ X$, there are $|S|k$ edges between $S$ and $N(S)$. If $|N(S)| < |S|$, then $\frac{|S|k}{|N(S)|} > k$, contradiction, so $|S| <= |N(S)|$. Hence there is a complete matching from $X$ to $Y$ by Hall's theorem.
    • Show that $G$ contains $k$ disjoint families of complete matchings on $X$..
      (proof.) Applying the above problem, we find a complete matching on $X$. Deleting the matching from $G$, we have a $(k−1)$-regular graph. Applying the above problem again on this $(k−1)$-regular graph, we find another complete matching on $X$. Repeating this process, we eventually find $k$ disjoint families of complete matchings on $X$.
    • Do you need to assume that $G$ is "simple" in the above problem? (Solution.) No, the above G can be graph with multiple edges, since Hall’s matching theorem also valid in such a graph.

Edge Coloring

Edge Chromatic number $χ'(G)$:

Let G be a graph without loops.

  1. A $k$-edge-coloring of $G$ is a function $f : E(G) → S$, for some set $S$ with cardinality $|S| = k$.
  2. The elements of $S$ are called colors.
  3. A $k$-edge-coloring $f$ is proper if $f(m) \ne f(m′ )$ for all edges $m, m′$ without common vertex.
  4. A graph is $k$-edge-colorable if it has a proper $k$-edge-coloring.
  5. The edge-chromatic number $χ'(G)$ is the least $k$ such that $G$ is $k$-edge-colorable.

Example.

$$\chi'(C_n) = \begin{cases} 2,& \text{if n is even}\ 3,& \text{if n is odd}\end{cases} $$ $$\chi'(P_n) = \begin{cases} 0,& \text{if n = 1}\ 1,& \text{if n = 2}\ 2,& \text{if n} \geq 3\end{cases} $$

$\chi'(K_{m,n}) = max(m,n)$

Lemma. $χ′(H) ≤ χ′(G)$ for any subgraph H of G.

Lemma. $χ′(H) \geq \Delta′(G)$

Line graphs

Idea. We convert all the edges of $G$ to the vertices. By doing so, we build a new graph $G'$ s.t. $\chi(G') = \chi'(G)$

The line graph $L(G)$ of $G$ is a graph with vertex set $VL(G) = EG$ and for $ℓ, ℓ′ ∈ VL(G)$, $ℓℓ′$ is an edge in $L(G)$ iff $ℓ, ℓ′$ have a common vertex in $VG$.

Remark.

  1. $χ′(G) = χ(L(G))$.
  2. $∆(L(G)) ≤ 2∆(G) − 2$.
  3. $∆(L(G)) \leq χ'(G) = χ(L(G)) ≤ ∆(L(G)) + 1 ≤ 2∆(G) − 1$

Let $α'(G)$ denote the maximum size of a matching in $G$.

We have $\alpha\prime(L(G))=\alpha(G)$, where $\alpha(G)$ is the number of maximum independent set.

Lemma. $χ′(G) ≥ |EG| α′(G)$

(Proof.) $χ′(G) = χ(L(G)) \geq \frac{|V_{L(G)}|}{\alpha(L(G))}=\frac{|EG|}{\alpha\prime(G)}$

Corollary. If $n$ is odd, then $χ′(K_n) ≥ n.$

(Proof.) $$χ′(K_n) = \frac{(^n_2)}{\frac{n - 1}2} = n$$

Corollary. If $n$ is odd, then $χ′(K_n) = n.$

We have seen $χ′(K_n) ≥ n$ in the last corollary, and $χ′(K_n) ≤ n$ by the following proper edge-coloring on $K_n$ with $VK_n = {0, 1, . . . , n − 1}$: $f(ij) = i + j \mod n$, which garantees that for any $j_1,j_2$, $f(ij_1)\ne f(ij_2)$.

Corollary. If $n$ is even, then $χ'(K_n) = n − 1$.

Connectivity

Definition

The connectivity of $G$, written $\kappa(G)$, is the minimum size of a vertex set $S$ such that $G - S$ is disconnected or has only one vertex.

The edge connectivity of $G$, written $\kappa\prime(G)$, is the minimum size of an edge set $F$ such that $G - F$ is disconnected.

Example.

  1. $\kappa(K_n) = n - 1$
  2. $\kappa\prime(K_n) = n - 1$
  3. $\kappa(K_{m,n}) = min{m, n}$
  4. $\kappa\prime(K_{m,n}) = min{m, n}$

Remark: $\kappa\prime(G) \leq \delta(G).$

Whitney Theorem

$$\kappa(G) \leq \kappa\prime(G).$$

(proof.)

If G is disconnected then $\kappa(G) = \kappa\prime(G) = 0$. Suppose G is connected. Pick an $F \subseteq$ such that $G - F$ is disconnected and $|F| = \kappa\prime(G)$. Suppose $VG = W \cup \bar{W}$ and $F$ is the set of edges with one end in $W$ and the other end in $\bar{W}$. If $|F| = |W||\bar{W}|$, then $$|F| \geq |W| + |\bar{W}| - 1 = |VG| - 1 \geq \kappa(G).$$

Otherwise, there exists a vertex $x \in W$ and a vertex $y \in \bar{W}$ such that $x, y$ are not adjacent. Defining the vertex subset $$S:=(N(x)\cap\bar{W})\cup{z\in W | z \ne x, N(z) \cap \bar{W} \ne \phi }.$$

Observe every path from $x$ to $y$ contains a vertex in $S$. Hence $G - S$ is disconnected, and then $\kappa(G) \leq |S| \leq |F| = \kappa\prime(G).$

The upperbound and lowerbound of edge connectivity is

$$\delta(G) \geq \kappa\prime(G) \geq \kappa(G).$$

$k$-cube $Q_k$

Definition

$$VG:={(a_1,a_2,\cdots,a_k) | a_i \in {0, 1}},$$ $$EG:={xy| x, y \in VG, |x-y| = 1}.$$

Such $G = Q_k$ is call $k$-cube.

Remark

  1. $Q_k$ has regular valency $k$.
  2. $Q_k$ is two copies of $Q_{k-1}$ with $2^{k-1}$ edges matching these copies.

Lemma

$\kappa(Q_k) = k$

(proof.)

Induction on k.

Basis: $k = 1$ since $\kappa(Q_i) = \kappa(K_2) = 1$. Induction: Assume $k \geq 2$.

Note that $\kappa(Q_k) \leq \delta(Q_k) = k$.

Suppose $S \subseteq V(Q_k)$ such that $Q_k - S$ is disconnected and $|S| = \kappa(Q_k)$.

Suppose $Q_{k - 1}, Q\prime_{k-1}$ are two copies whose union is $Q_k$.

Suppose for this moment that $Q_{k - 1} - S$ and $Q\prime_{k - 1} - S$ are both connected. Then all matching between $Q_{k - 1}$ and $Q\prime_{k - 1}$ must be broken. Hence $|S| \geq 2^{k - 1} \geq k$ and we are done. Next suppose $Q_{k - 1} - S$ and $Q\prime_{k - 1} - S$ is disconnected. Say that $Q_{k - 1} - S$ is disconnected. By induction, we have $|S \cap VQ_{k-1}| \geq \kappa(Q_{k - 1}) = k - 1$. Note that $S \cap VQ\prime_{k-1} \ne \phi$. Hence $|S| \geq k - 1 + 1$.

$k$-connected graph

A graph $G$ is $k$-connected if $\kappa(G) \geq k$.

Equivalently $G - S$ is connected for any subset $S \subseteq VG$ of cardinality $k - 1$.

Remark.

  1. A $1$-connected graph is connected.
  2. If $\kappa(G) = k$, then $G$ is $t$-connected for $t \leq k$.

Internally disjoint paths

Let $u, v$ be two vertices in $G$. Two $u, v$-paths are internally disjoint if they have no common internal vertex.

Lemma.

Suppose for any two distinct vertices $u,v$ there exist internally disjoint $u, v$-paths in G. Then G is $2$-connected.

(proof.)

We need to prove that $G - x$ is connected for any $x \in VG$. Pick two vertices $u, v$ in $G - x$. At least one of the $u, v$-paths is in $G - x$. Hence $G - x$ is connected.

For $u, v ∈ VG$, let $∂(u, v)$ be the length of shortest $u, v$-path. $∂(u, v)$ is called the distance of $u, v$.

Theorem 32.2 (Whitney):

Suppose G is 2-connected with at least three vertices. Then for any two distinct vertices $u, v$ there exist internally disjoint $u, v$-paths in G.

(proof.)

Induction on the distance $\delta(u, v)$.

Basis: $\delta(u, v) = 1$. Hence uv is an edge. Because $\kappa\prime(G) \geq \kappa(G) \geq 2$, $G - uv$ is connected.

Indunction: Assume this theorem is true for $\delta(u, v) \leq k$. Now assume $\delta(u, v) = k + 1$. Pick a vertex $w$ with $\delta(u, w) = 1$ and $\delta(w, v) = k$. By induction, we can find two internally disjoint $w-v$ paths $P$ and $Q$. Since $G - w$ is connected, we can find a $u, v$-path $R$ in $G - w$. Let $z$ be the first vertex in $R$ that meets $P$ or $Q$, say $P$. Then the combine of $u, z$-path of $R$ with $z, v$-path of P is internally disjoint from the path $uw \cup Q$.

Expanding Lemma:

Suppose $G$ is 2-connected and $G\prime$ is obtained from $G$ by adding a new vertex $y$ with at least 2 neighbors in $G$. Then $G\prime$ is 2-connected.

Characterization Theorem

Let $G$ be a graph with at least three vertices. Then the following (i)-(iv) are equivalent.

  1. $G$ is 2-connected.
  2. For all vertices $u, v \in V$, there are internally disjoint $u, v$-paths.
  3. For all vertices $u, v \in V$, there is a cycle through $u$ and $v$.
  4. $\delta(G) \geq 2$ and every pair of edges in $G$ lies on a common cycle.

(proof.)

$4 \rightarrow 3$ is clear. $3 \rightarrow 2$ is clear. $2 \rightarrow 1$ is Whitney theorem. $1 \rightarrow 4$:

$G$ is connected with at least 2 vertices, every vertex has degree at least 1. $\delta(G) ≥ 2$ follows from the second statement. Let $uv$ and $xy$ be two edges in $G$. Add to $G$ a new vertex $s$ with neighborhood ${u, v}$ and another new vertex $t$ with neighborhood ${x, y}$. Since $G$ is 2-connected, the Expansion Lemma implies the new graph $G′$ is 2-connected. By Whitney Theorem, there are two internally disjoint $s, t$-paths $P, Q$ in $G$ . Note that $u, v$ (resp. $x, y$) are in different paths since $s$ (resp. $t$) has degree 2. Say $u,x ∈ P$ and $v,y ∈ Q$. Let $C$ be the cycle combining the $s,t$-path $P$ and the $t, s$-path of reversed Q. Note that $v, s, u$ and $x, t, y$ are two paths of length 2 in $C$. Replacing $v, s, u$ and $x, t, y$ by $v, u$ and $x, y$ respectively yields the desired cycle through $vu$ and $xy$.

Given nonadjacent vertices $x,y ∈ VG$, a set $S ⊆ VG − {x,y}$ is an $x,y$-cut if $G − S$ has no $x, y$-path.

Let $\kappa(x, y)$ be the minimum size of an $x, y$-cut. Let $\lambda(x, y)$ be the maximum size of a set of pairwise internally disjoint $x, y$-paths.

Remark:

  1. $\kappa(x, y) \geq \kappa(G)$ for all $x, y \in VG$.
  2. $\kappa(x, y) = 1 \rightarrow \lambda(x, y) = 1$.

Lemma.

$\lambda(x, y) \leq \kappa(x, y)$.

(Proof.) Let $S$ be an $x, y$-cut of size $\kappa(x, y)$. Note that each $x, y$-path contains at least a vertex in $S$. Hence $\lambda(x, y) \leq \kappa(x, y)$.

Remark: Suppose $\kappa(G) = \kappa(x, y) = 2$. Then $\lambda(x, y) \geq \kappa(x, y)$ by the characterization of 2-connected graph.

Theorem 32.4 (Menger)

$λ(x, y) = κ(x, y)$ for any nonadjacent vertices $x, y$ in $G$.

(proof.) Skip.

Lemma:

A connected and locally $(k − 1)$-connected graph $G$ (i.e. $G_1(x)$ is $(k − 1)$-connected for all $x ∈ VG$) is $k$-connected.

第四次作業

  1. Let $G_{m,n} = (V,E)$ be an $m×n$ grid, where $V = {(i, j)|1 ≤ i ≤ m,1 ≤ j ≤ n}$ and $E = {(i, j)(k,l)||k−i|+|l− j| = 1}$, where $m,n ≥ 3$.

    • Show that $χ(G_{m,n})$ = 2.

      $G_{m, n}$ is bipartite with bipartition $X = {(i, j) | i + j is event}$ and $Y = {(i, j) | i + j is odd}$. As $G_{m, n}$ has an edge, $\chi(G_{m, n}) = 2$.
    • Show that $χ′(G_{m,n})$ = 4.

      $\chi\prime(G_{m, n}) \geq \Delta(G_{m, n}) = 4$, and we can paint the vertical edges by using two colors alternately and similarly paint horizental edges by using another two colors. Hence we have $\Chi\prime(G_{m, n}) \leq 4$.

  2. Determine $χ′(Q_k)$, where $Q_k$ is $k$-cube.

    Since $Q_k$ is bipartite, $\chi\prime(Q_k) = \delta(Q_k) = k$ by König Theorem.

  3. Prove Menger’s Theorem: For nonadjacent vertices $x, y$ in graphs: $κ (x, y) = λ (x, y)$.

It is clear $λ(x,y) ≤ κ(x,y)$ in $G$. To prove $λ(x,y) ≥ κ(x,y)$ , We shall construct $κ (x, y)$ internally disjoint $x, y$-paths. Define a network $G$ from $G$ as follows. Let $V\vec{G} :={u^−,u^+ |u∈VG−{x,y}}∪{x,y}$, where $x$ is source and $y$ is sink. Replace an edge $xu$ in $G$ by a directed edge $xu^−$ and an edge $uy$ by a directed edge $u^+y$ with integral capacity $t = |VG|$. Replace the remaining edges $uv$ by a directed cycle $u^− u^+ v^− v^+ u^−$ with capacities $1,t,1,t$ respectively. For an $x,y$-cut $S$ in $G$ the set

$$S\prime :={w | w \text{ is in an } x,u^- \text{ -path disjoint from } u^+ \text{ for } u∈S}$$

is a cut in $\vec{G}$. One can check that if $s\notin S$ and $s^- ∈ S\prime$ then $s^+ ∈S\prime$. Hence the cut $S\prime$ in $\vec{G}$ has capacity at most $|S|$, and indeed has capacity $|S|$ if $|S| = \kappa(x, y)$. Conversely for a cut $S\prime$ in $\vec{G}$ with capacity less than $t$ the set $$T:={u\in VG | u^- \in S\prime, u^+ \notin S\prime }$$ is an $x, y$-cut in $G$, and indeed $T' = S'$. This proves that the network has minimum cut capacity $\kappa(x, y)$. By max-flow-min-cut theorem and integrality theorem, there exists an integer flow with value $\kappa(x, y)$. Due to the setting, this flow has value on an edge either $0$ or $1$. Hence one can easily construct $\kappa(x, y)$ internally disjoint $x, y$-paths in $G$ from this integral flow in $\vec{G}$. This proves $\lambda(x, y) \geq \kappa(x, y)$.

Planar Graphs

A graph is planar if it has a drawing in $\mathbb{R}^2$ without crossings. A plane graph is a particular drawing of a planar graph in $\mathbb{R}^2$.

Example:

$K_{2, m}$ and $K_4$ are both planar.

Faces

Let $G$ be a plane graph. Then $\mathbb{R}^2 - G$ is a finite disjoint union of "maximal connected open sets". Each of these maximal connected open sets is called a face of $G$.

Euler’s Formula

Let $G$ be a connected plane graph with $n$ vertices, $e$ edges and $f$ faces. Then $n − e + f = 2$.

(proof.) Induction on $n$.

Basis: $n = 1, e = 0, f = 1 \rightarrow n - e + f = 2$. Induction Step: Since $G$ is connected, we can find an edge $e$ which is not a loop. By contracting $e$ to a point, we obtain a new graph $G/e$ with $n - 1$ vertices, $e - 1$ edges, and $f$ faces. Then $(n - 1) - (e - 1) + f = n - e + f = 2$.

Euler’s Formula(in Disconnected Graph):

Let $G$ be a plane graph with $n$ vertices, $e$ edges and $f$ faces. Then $n − e + f = 1 + c$, where $c$ is the number of connected components.

(proof idea.) Induction on $c$.

Theorem(Upper Bound of Edge Numbers)

Let $G$ be a simple planar graph with at least 3 vertices. Then $$|EG| \leq 3|VG - 6.$$

If $G$ is triangle-free, then $|EG| \leq 2|VG| - 4$.

(Proof.) By adding more edges, we might assume G is connected. Note that each edge is in the boundary of at most two faces and each face contains at least 3 edges as boundaries. Using 2-way counting in the set $${(m, F) | m is an edge in the boundary of face F}.$$

We obtain $|EG| \times 2 \geq f \times 3$, or $|EG| \times 2 \geq f \times 4$ if $G$ is triangle-free(each face contains at least 4 edges as boundaries). Using this and Euler formula we have the lemma.

Corollary

$K_5$ and $K_{3,3}$ are not planar.

$K_5$ has 5 vertices and 10 edges violating $|EG| \leq 3 |VG| - 6$.

$K_{3,3}$ is triangle-free, and has $6$ vertices and $9$ edges, violating $|EG| \leq 2|VG| - 4/$

Remark.

Any graph containing a subgraph $K_5$ or $K_{3,3}$ is not planar.

Corollary

$\delta(G) \leq 5$ for simple planar graphs

Otherwise, $$6|VG| \leq \sum_{x \in VG} deg(x) = 2|EG| \leq 2(3|VG| - 6) _{\rightarrow!\leftarrow}.$$

Four Color Theorem

Five Color Theorem

$\chi(G) \leq 5 for any simple planar graphs G.$

(Proof.） I cannot understand :(

Four Color Theorem: This is proved by computer.

Subdivision

In a graph $G$, subdivision of an edge $xy$ is the operation of replacing $xy$ with a path x, w, y through a new vertex w. A subdivision of $G$ is a graph obtained from a sequence of subdivision processes starting from $G$.

The strong condition to planar graph

A graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_{3,3]$.

Hamiltonian Cycles

A Hamiltonian cycle (resp. Hamiltonian path) of $G$ is a cycle (resp. path) that contains all vertices of $G$.Hamiltonian path is also called spanning path.

A graph is Hamiltonian if it contains a Hamiltonian cycle.

Example.

  1. $K_n$ is Hamiltonian if $n \geq 3$.
  2. $K_{m,n}$ is Hamiltonian if and only if $m = n ≥ 2$.

Lemma (Necessary Conditions to Hamiltonian):

(Proof.) Suppose $G$ is Hamiltonian and $S ⊆ VG$ is nonempty. Then $c(G−S) ≤ |S|$, where $G−S$ is the subgraph of $G$ induced on $VG−S$, where $c(G)$ is the number of connected components in $G$. Then $$c(G−S) ≤ c(C−S) ≤ |S|.$$

Ore Theorem, 1960

Let $G$ be a simple graph such that $deg(u) + deg(v) ≥ |VG|$ for any nonadjacent vertices $u, v$. Then $G$ is Hamiltonian.

A Lemma inspired from Ore Theorem:

Let $G$ be a simple connected graph containing two nonadjacent vertices $u, v$ such that such that $deg(u) + deg(v) ≥ |VG|$. If $G + uv$ is Hamiltonian, then $G$ is Hamiltonian.

Chvátal Theorem, 1972

Let G be a simple graph with vertex degrees $d_1 ≤ · · · ≤ d_n$, where $n≥3$. If $d_i >i$ or $d_{n−i} ≥n−i$ for any $i<\frac{n}2$, then $G$ is Hamiltonian.

(proof.) The graph $K_n$ is clearly Hamiltonian. Suppose graph $G$ of order $n$ with maximum number of edges satisfying the assumption is not Hamitonian. By previous lemma, we can assume $\deg(u) + \deg(v) < n$ for any nonadjacent vertices $u, v$ in $G$. Pick two nonadjacent vertices $u, v$ with maximum degree sum $\deg(u) + \deg(v)$. Without loss of generality, assume $i = deg(u) ≤ deg(v) = j$. As the choice of $u, v$, those $n − j − 1$ vertices not $v$ and not adjacent to $v$ must have degrees at most $i$, the degree $u$, and $n - j - 1 \geq (i + j + 1) - j - 1 = i$, we have $d_i \leq i.$ Similarly, those $n−i$ vertices not adjacent to $u$ (so including $u$) must have degrees at most $j$, the degree of $v$, we have $d_{n−i} ≤ j < n − i$, a contradiction.

Exercise:

There is no graph with degree sequence 1,3,4,4,5,5,6,8,8.

(Sol.) By the Chvátal Theorem, we know $G$ is hamiltonian. But because $d_1 = 1$, therefore $G$ is not hamiltonian, contradiction.

Connectivity and independent number

The connectivity of $G$, written $κ(G)$, is the minimum size of a vertex set $S$ such that $G − S$ is disconnected or has only one vertex.

The independent number of $G$, written $α(G)$, is the maximum number of pairwise nonadjacent vertices.

Lemma: If $G$ is a graph with $δ(G)≥2$, then $G$ has a cycle of length at least $δ(G)+1$.

(proof.) Set $δ = δ(G)$. Let $P$ be a maximal path in $G$ and let $v$ be an end of $P$. By assumption, $v$ has at least $δ$ neighbors all of which must lie on $P$ . If $u$ is the neighbor of $v$ which is furthest from $v$ on $P$, then the subpath of $P$ from $v$ to $u$ together with $uv$ is a cycle of length at least δ+1.

Chvátal-Erdős Theorem, 1972

Suppose $G \ne K_2$ and $κ(G) ≥ α(G)$. Then $G$ is Hamiltonian.