圖論整理第一部分

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

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$

Trees and forests

• Forest: A graph with no cycles
• Tree: A connected forest
• Leaf: A vertex of degree 1
• Root: A vertex of degree $d=1$, such tree is called a rooted tree
• Chain: The down-closure of every vertex

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