4.21 Graphs

Track the relations between object

Example: road map of cities and road that connect them

Simple Labelled Graph

A simple labelled graph \(\Gamma\) is a pair \(\Gamma=(V,E)\) where \(V\) is the set of vertices of \(\Gamma\) and \(E\) is a subset of unordered pairs of distinct element of \(V\), that is the edges of \(\Gamma\)

As the example above, edges can be (Chengdu, Guangzhou), (Guangzhou, Shantou),...

And this graph is same with above pic. We only care vertices and edges.

Vertex and Edge

A degree of a vertex \(v\in V\) of a graph \(\Gamma=(V,E)\) is \(\#\{e\in E:v\in e\}=\deg (v)\) (The number of edges the vertex \(v\) belongs to)

When a vertex \(v\) belongs to an edge \(e\), we say that \(v\) and \(e\) are incident

When edge \(e=(v_1,v_2)\), we say that \(v_1\) and \(v_2\) are adjacent.

The handshaking lemma

Let \(\Gamma=(E,V)\) be a finite (\(\#\text{vertices}<\infty\)) simple graph, then \(2\#E=\sum_{v\in V}\deg(v)\)

Example: Take above pic as an example

\(\sum\deg=1+2+3+4+1+1+0=12=2\#E\)

Proof

Let's count the number of pairs: \(P=\{(v,e)\in V\times E:v\text{ is incident to }e\}\)

If we fix \(v_0\in V\), \(\#\{(v_{0},e)\}=\deg v_{0}\). If we fix \(e_0\in E\), \(\#\{(v,e_0)\}=2\) (illustration:)

Then \(\#P=\sum_{v_0\in V}\deg v_0=\sum_{e_0\in E}2=2\#E\)

Graph isomorphism

We say the labelled graphs \(\Gamma_{1}=(V_{1},E_{1})\) and \(\Gamma_2=(V_2,E_2)\) are labelled if there exist a bijection \(f:V_1\to V_2\) such that \((v_{1},v_{2})\in E\iff(f(v_1),f(v_2))\in E_2\)

(Graph isomorphism is an equivalence relation on the set of graphs)

Subgraphs

Let \(\Gamma=(V,E)\) and \(\Gamma'=(V',E')\) are two graphs, we say that \(\Gamma\) is a subgraph of \(\Gamma'\) ( \(\Gamma\leq \Gamma'\) ) if \(V\subseteq V'\) and \(E\subseteq E'\)

Notice: It is not required that if \(v_1\) and \(v_2\) are adjacent in \(\Gamma'\), they are adjacent in \(\Gamma\)

Induced Subgraph

Let \(\Gamma'=(V',E')\) be a graph such that \(V\subseteq V'\), then \(\Gamma'[x]\) is a subgraph of \(\Gamma'\) defined by the following conditions

Set of vertices is \(V\)
\(v_1\) and \(v_2\) are adjacent in \(\Gamma'[x]\) iff they are adjacent in \(\Gamma'\)

Some Important Classes of Graphs

Empty or discrete graph \(E_n\) (\(D_n\)), that is \(n\) vertices with \(0\) edges

* Complete graph \(K_n\), that is \(n\) vertices and every vertices are adjacent * Cycle graph \(C_n\), that is \(n\) vertices and adjacent to form a cycle * Path graph \(P_n\), that is \(n\) vertices and adjacent to form a path

UV-WALK

Let \(\Gamma =(V,E)\) be a graph and \(u\),\(v\) are two vertices of \(\Gamma\) (not necessary different)

A UV-WALK in \(\Gamma\) is a sequence walk of length \(n+1:\) \(u\overset{e_0}{-}w_{1}\overset{e_1}{-}w_{2}\overset{e_2}{-}w_{3}\overset{e_3}{-} ...\overset{e_{n-1}}{-}w_{n}\overset{e_{n}}{-}v\) where \(w_1,...,w_n\) are vertices of \(\Gamma\) and \(e_1,...,e_n\) are edges of \(\Gamma\)

Here, \(u\) is adjacent to \(w_1\) via \(e_0\), \(w_{i}\) is adjacent to \(w_{i+1}\) via \(e_{i}\), ..., \(w_n\) is adjacent to \(v\) via \(e_n\)

Example

length: 7

We say that \(\Gamma=(V,E)\) is connected if \(\forall\) two vertices \(u,v\in V\), there is a uv-walk between them.

Acyclic

A graph \(\Gamma=(V,E)\) is acyclic if there are no subgraphs of \(\Gamma\) isomorphic to \(C_n\) for \(n\geq 3\)

A graph \(\Gamma=(V,E)\) is a tree if it is connected and acyclic:

UV-path

A uv-path in \(\Gamma(V,E)\) is a subgraph of \(\Gamma\) isomorphic to \(P_n\) for some \(n\geq 2\) such that the degree \(1\) vertices of \(P_n\) are mapped to \(u\) and \(v\) respectively

(See the black lines)

Remark: UV-walk can go through a repeated vertex but U

v-path cannot.

Lemma

If \(\Gamma\) is a graph and there is a uv-walk in \(\Gamma\), then there is a uv-path in \(\Gamma\)

Idea: If every two vertices in a walk are different, then we have a path

Suppose there is a vertex \(w\) in the walk, that is encountered more than once

Reduces the numbers of appearance of vertex \(w\) by \(1\), do until we have a path.

Proposition

Let \(\Gamma=(V,E)\) be a graph and \(\min_{v\in V}\deg\left(v\right)=\delta\geq2\), then \(\Gamma\) has a path of length \(\delta\) and a cycle of length at least \(\delta+1\)

Proof

Let \(P=(v_0,...,v_k)\) be a longest path in \(\Gamma\), denote \(W=\{v_0,...,v_k\}\) and \(\#W=k+1\)

Notice that every vertex adjacent to \(v_0\) is an element of \(W\), otherwise we can make a longer path, which would produce a contradiction

Thus \(\#W\geq \deg(v_{0})\geq \delta\)

Let \(i\in \{1,...,k\}\) be the largest number such that \(v_i\) is adjacent to \(v_0\)

Clearly, \(i\geq \delta\), connect \(v_i\) to \(v_0\) forming a cycle

Illustration:

Corollary

Every tree has a leaf. (leaf is a degree \(1\) vertex)

Suppose \(Г\) has no leaves, then \(\delta \ge 2\)

Then by corollary, it has a cycle of at least \(\delta+1\)
Then it is not acyclic, by definition it is not a tree.

Proposition

Let \(\Gamma=(V,E)\) be a tree and \(\#V=n\), then \(\#E=n-1\)

Proof

Induction on \(n\)

Base case: \(n=1\), \(1\) vertex and \(0\) edges

Induction step: Suppose we know it for all trees up to \(n-1\) vertices.

Take a tree on \(n\) vertices, by corollary it has a leaf. Remove the leaf, it gives a tree.

Then applied hypothesis, \(n-1\) vertices, \(n-2\) degrees to \(n\) vertices, \(n-1\) degrees

‍