圖論整理第一部分

寫一些課本、課堂、網路上的扣扣、圖待增。持續更新中…

1. Graphs

Define a graph

A pair of sets $G=(V, E)$ such that $E \subseteq \{\{u, v\} | u, v \in V\}$

Some notations

• $V(G)$: vertix set
  elements of $V$ are called vertices / nodes / points
  e.g. $V(G) = \{a, b, c, d\}$
• $E(G)$: edge set
  elements of $E$ are called edges / arcs / lines
  e.g. $E(G) = \{ab, ac, ad, bc, bd\}$
• Incident: $v$ is incident with $e$ if $v \in e$
  The set of all edges incident with a vertex $v$ is denoted by $E(v)$
• Adjacent / Neighbouring: $u, v$ are adjacent if $\{u, v\} \in E$
• Indepedent / Stable set: $u, v$ are independent if $\{u, v\} \notin E$

Types of graphs

• $\phi$: empty graph
• Trivial graph: graph of order 0 or 1

Subgraphs

• Induced subgraph: subgraph of $G$ with some vertices removed, and all edges between them removed as well.
• Spanning subgraph: subgraph of $G$ with all vertices of $G$
• Line graph: subgraph of $G$ with all edges of $G$
• Improper subgraph: subgraph of $G$ with all edges of $G$, otherwise proper subgraph.

Properties of graphs

• Complete: every pair of distinct vertices are adjacent, denoted by $K_n$

Homorphisms

Let $G=(V,E), G'=(V',E')$ be graphs.
A homomorphism from $G$ to $G'$ is a function $\psi: V\to V'$ such that $xy \in E \Rightarrow \psi(x)\psi(y) \in E'$

Isomorphic

If $\psi$ is a bijection and its inverse image is a homomorphism, then $\psi$ is an isomorphism and $G$ is isomorphic to $G'$, written as $G \cong G'$

Degree of a vertex

Let $G=(V,E)$ be a non-empty graph.

• $N(v)$: The set of neighbours of a vertex $v$
• $d(v)$ or $d_{G}(v)$: The degree or valency of a vertex $v$
  • isolated vertex: A vertex of degree 0 is called an
  • $\Delta(G)$: The maximum degree of $G$
  • $\delta(G)$: The minimum degree of $G$
  • k-regular / regular: All vertices of $G$ have the same degree

Some Formula

• Average degree of $G$: $\displaystyle d(G) := \frac{1}{|V|}\sum_{v\in V}d(v)$
• $\displaystyle |E| = \frac{1}{2}\sum_{v\in V}d(v)=\frac{1}{2}\sum_{v\in V}d_(v) \cdot |V|$

Prop. 2.1
As $\displaystyle |E| = \frac{1}{2}\sum_{v\in V}d(v)$ is an integer, $\displaystyle \sum_{v\in V}d(v)$ is even

Prop. 2.2
Every graph $G$ with at least one edge has a subgraph $H$ with $\delta(H)\geq \varepsilon (H)\geq \varepsilon (G)$

Paths and cycles

Paths

Non-empty graph $G=(V,E)$
A sequence of vertices $v_0, v_1, \cdots, v_n$ such that $v_iv_{i+1}\in E$ for $0\leq i\leq n-1$

• walk: A sequence of vertices $v_0, v_1, \cdots, v_n$ such that $v_iv_{i+1}\in E$ for $0\leq i\leq n-1$
• trail: A walk with no repeated edges
• circuit: A walk with no repeated vertices except thefirst and last

Cycles

A circuit with no repeated edges except the first and last

• Girth: The minimum length of a cycle
• Circumference: The maximum length of a cycle
• Chord: An edge joining two vertices of a cycle but not part of the cycle
• Distance: The length of the shortest path between two vertices
• Diameter: The maximum distance between two vertices

Prop. 1.3
Every graph $G$ contains a path of length $\delta(G)$ and a cycle of length at least $\delta(G)+1$

Prop. 1.4
A graph $G$ of radius at most $k$ and maximum degree at most $d\geq 3$ has fewer than $\displaystyle \frac{d(d-1)^k}{d-2}$ vertices

Thm. 1.5
Let $G$ be a graph.
If $d(G)\geq d\geq 2$ and $g(G)\geq g\in \mathbb{N}$, then $|G|\geq n_0(d,g)$

Cor. 1.6
If $\delta(G)\geq 3$ then $|G|<2\log|G|$

Connectivity

• Connected: A graph is connected if there is a path between every pair of vertices
• Component: A maximal connected subgraph, it is also a induced subgraph

Thm. 1.7
Let $0\neq k\in \mathbb{N}$.
Every graph $G$ with $d(G)\geq 4k$ has a $(k+1)$-connected subgraph $H$ with $\epsilon(H)\geq \epsilon(G)-k$

1.5 Trees and forests

forest / tree / leaves

A acyclic graph is a forest. A connected forest is a tree. A vertex of degree 1 is a leaf

root / tree-order

• root is the least element in its tree-order
• Define a partial ordering on the vertices of a tree $T$, where $x\leq y$ for $x\in rTy$.
  As an expression of height: $\lfloor x \rfloor := \{y|y\geq x\}$(down-closure of y) and $\lceil y \rceil := \{x|y\geq x\}$(up-closure of x)

  背法：$\lceil y \rceil$的話，$y$是最高的，所以$x$是包含$y$的所有點；$\lfloor x \rfloor$的話，$x$是最低的，所以是包含$y$的所有點

height / level / normal tree

• chain: the down-closure of every vertex is a chain
• height: the vertices at distance $k$ from the root have height $k$ and form the $k$-th level of $T$
• normal tree: a rooted tree $T$ contained in a graph $G$ is called normal if the ends of every $T$-path are comparable in the tree-order of $T$

Thm.
The following assertions are equivalent for a graph $T$:

1. $T$ is a tree
2. Any two vertices of $T$ are linked by a unique path in $T$
3. $T$ is minimally connected, i.e. $T$ is connected but $T-e$ is disconnected for any $e\in E(T)$
4. $T$ is maximally acyclic, i.e. $T$ contains no cycle but $T+xy$ does for any two non-adjacent vertices $x, y\in T$

Bipartite graphs

A graph $G=(V,E)$ is r-bipartite : $V$ admits a partition into r classes such that every edge has its end in different classes

Complete bipartite graph

An r-bipartite graph with every two vertices from different partitions are adjacent, denoted by $K_{m,n}$

• star: $K_{1,n}$
• centre: The vertex in the singleton partition class of a star

Prop.
A graph is bipartite if and only if it contains no odd cycle

Proof:

• $\Rightarrow$: Suppose $G$ is bipartite with partitions $V_1, V_2$, let $C=(v_1, v_2, \cdots, v_n, v_1)$ be a odd cycle in $G$, where $v_i\in V_1$ if $i$ is odd, $v_i\in V_2$ if $i$ is even. we know from our assumption that $C$ is an odd cycle, so $v_1$ and $v_n$ are in the same partition, however, by the definition of bipartite graph, $v_1$ and $v_n$ are in different partitions, a contradiction.
• $\Leftarrow$: Let $G$ be a graph with no odd cycles, we can partition $V$ into $V_1, V_2$ by the parity of the distance from a fixed vertex $v_0$.
  Suppose $v_0\in V_1$, then $v\in V_1$ if the distance from $v_0$ to $v$ is even, otherwise $v\in V_2$.
  1. First, we need to prove that $a\neq b\neq c$, wlog, let $a, b\in V_1$ or $V_2$, then $a, b$ are in the same partition, so $ab$ is not an edge, which is a contradiction. Wlog, suppose there exist $a, b, c\in V_1$ or $V_2$ such that $ab\in E(G)$.
     Let $a=c$, then $d(a, c)=0$. $d(a, b)$ and $d(b, c)$ are even.
     However $d(a, b)=1$, which is a contradiction. So $a\neq b\neq c$.
  2. Second, let $P$ be the shortest path between $a$ and $c$, $Q$ be the shortest path between $b$ and $c$, that $P$ and $Q$ have the same parity, they start at $c$ but can also have another common vertex, label it as $d$.
     The path $P$ is separated by $d$ into two parts, $P_1$ and $P_2$, $P_1$ is the part from $c$ to $d$, $P_2$ is the part from $d$ to $a$.
     The path $Q$ is separated by $d$ into two parts, $Q_1$ and $Q_2$, $Q_1$ is the part from $c$ to $d$, $Q_2$ is the part from $d$ to $b$.
     To have the shortest path, the length of $P_1$ and $Q_1$ are the same, $|P|=|P_1|+|P_2|, |Q|=|Q_1|+|Q_2|$, so $|P_2|=|Q_2|$.
     Therefore, $|P_{2}^{-1}Q_2(a)|=|P_2|+|Q_2|+1=2k+1$, where $k\in \mathbb{N}$ is an odd cycle, which contradict our assumption that $G$ has no odd cycle.