The Basics

A graph is a pair $G=(V,E)$ , $ G $ are vertics, and $E$ means edges, $E$ are 2-element subsets of $V$.

A vertices $v$ is incident with an edge $e$ if $v\in e$,two vertices incident with an edge are endvertices or ends.The set of all the edges in $E$ at a vertices $v$ is denoted by $E(v)$.

Some concept:

• graph’s order written as $|G|$, means the number of vertices. The number of edge denoted by $||G||$. empty graph $(\emptyset,\emptyset)$ simply write $\emptyset$, A graph of order 0 or 1 is called trivial.

• adjacent or neighbours : vertices have an edge ; edge have an end in common

• complete : all vertices of a graph are pairwise adjacent. A complete graph on $n$ vertices is a $K^n$, example $K^3$ is a triangle(三角形).

• independent : non-adjacent; for a set, if no two of its elements are adjacent.

• isomorphic ， write $G \simeq G^\prime$ (usually like write $G = G^\prime$), if two graphs exists a bijection (双射) $$\varphi : V \to V^\prime ,\text{with} ,, xy\in E \Leftrightarrow \varphi (x)\varphi(y) \in E^\prime \quad \forall x,y\in V$$

  so the map $\varphi$ called isomorphism , if $G = G^\prime$ is automorphism (自同态（形）).

• graph property : A class of graphs that is closed under isomorphism.

• graph invariant : A map which assigns equal values to isomorphic graphs. (在同形图上不变的量，比如节点数量和边数量)

Set operation :

• Union : $G \cup G^\prime := (V\cup V^\prime,E\cup E^\prime)$, difference similarly, and if $G\cap G^\prime = \emptyset$, then they are disjoint.

• induced subgraph : $G \subseteq G^\prime$ and $G^\prime $ has all the edge $xy\in E$ with $x,y \in V^\prime$. write $G^\prime =: G[V^\prime]$. (只少了点的子集，包括的点同时包括所有对应边)

• spanning subgraph : $G \subseteq G^\prime$ and $V^\prime$ spans all of $G$, i.e. if $V^\prime=V$. (点都有的子图)

• $G - U$ is $G [V\setminus U]$, $U$ is any set of vertices. Similarly, $G+F := (V,E\cup F)$.

• $G* G^\prime$ : $G$ and $G^\prime$ is disjoint, and joining all vertices with each other. For example, $K^2 * K^3 = K^5 $.

• complement : write is $\overline{G}$, $\overline{G} = G ([V]^2 \setminus E ) $

• line graph : $L(G)$ of $G$ is the graph on $E$, which edges as vertices and adjacent edges as edges. (边视为顶点的新图)

degree of a vertex

The set of neighbours of a vertex $v$ in $G$ is denoted by $N_G(v)$ or $N(v)$, for a set $U\subseteq V$, $N(U)$ means the neighbours in $V\setminus U$ for all vertices in $U$. The degree $d(v)$ is the number $|E(v)|$ of edges at $v$.

isolated meaning a vertex degree is 0, $\delta(G)$ and $\Delta(G)$ is the minimum degree and maximum degree of $v\in V$.

$d(G)$ is the average degree of $G$, sometimes directly express as $\varepsilon(G) := |E|/|V|$, and $\varepsilon(G) = \frac{1}{2} d(G)$.

• $k$-regular : all the vertices of $G$ have same degree $k$. cubic is a 3-regular graph.

Proposition : The number of vertics of odd degree in a graph is always even

Paths and cycles

A path is a non-empty graph $P=(V,E)$ of the form: $$V={x_0,x_1,……, x_k} \quad E={x_0x_1,……,x_{k-1}x_k}$$

The number of edges of a path is its length, denoted by $P^k$. $P^0 = K^1$.

• A-B path : path $P = x_0…x_k$ and $V(P)\cap A={x_0} \quad V(P)\cup B={x_k}$
• independent paths : none of them contains an inner vertex of another.(互不包含中间节点)
• H-path : $P$ two ends in graph H

cycle : $P = x_0…x_{k-1}$ is a path and $k\ge 3$, the graph $C^k := P + x_{k-1}x_0$.

• girth $g(G)$ : The minimum length cycle of $G$ .(no cycle is zero)
• circumference : The maximum length cycle of $G$.(no cycle is $\infty$)
• chord : two vertices of a cycle joining a edge but not be the edges of the cycle
• induced cycles : The cycle is a subgraph of other cycle
• diam $G$ : The greatest distance between any two vertices of $G$

Proposition : Every graph containing a cycle satisfies $g(G)\le 2 ,\text{diam} ,G + 1$

• central : A vertex in $G$ its greatest distance with any other vertex is smallest. And this distance is the radius of $G$, denoted by $rad G$

$$rad, G \le diam ,G \le 2 , rad , G$$

Corollary : If $\delta (G) \ge 3$ then $g(G) < 2 log|G|$.

• walk : If the vertices in a walk are all distinct, is a path.
• connected : any two of vertices are linked by a path in graph $G$
• component : 图的一个最大联通子图
• separates : 如果所有A-B路径都需要经过X的点或边，称X分割了A、B。 edges of X, deifnition of bridge. two vertics is a cutvertex.

Just Words

• nuisanse : 麻烦事
• disregard ：不理会