Graph
in Discrete Mathematics with 7 comments

// 汉密尔顿图充分条件证明

# Graph

## Introduction to Graphs

Definition:

• A simple graph $G=(V,E)$ consists of $V$, a nonempty set of vertices, and $E$, a set of unordered pair of distinct elements of $V$ called edges.
• A multigraph $G=(V,E)$ consists of a set $V$ of vertices, and a set $E$ of edges,and a function from $E$ to $\left\{\left\{u,v\right\}|u,v\in V,a\neq v\right\}$. The edge $e_1$ and $e_2$ are called multiple or parallel edges if $f(e_1)=f(e_2)$.
• A pseudograph $G=(V,E)$ consists of a set $V$ of vertices and a set $E$ of edges, and a function from $E$ to $\left\{\left\{u,v\right\}|u,v\in V\right\}$. An edge is a loop if $f(e)=\left\{u,u\right\}=\left\{u\right\}$ for some $u\in V$.

Remark:
To summarize,

• Pseudograph are the most general type of undirected graphs since they contain loops and mutiple edges.
• Multigraphs are undirected graphs that may contain multiple edges but not have loops.
• Simple graph are undirected graphs with no multiple edges or loops.

Definition:

• A directed graph $G=(V,E)$ consists of a set of vertices $V$, and a set of edges $E$ that are ordered pairs of elements of V.
• A directed multigraph $G=(V,E)$ consists of a set of $V$ of vertices and a set $E$ of edges, and a function from $E$ to $\left\{\left\{u,v\right\}|u,v\in V,a\neq v\right\}$. The edges $e_1$ and $e_2$ are called parallel edges if $f(e_1)=f(e_2)$.
Table 1 GRAPH THERMINOLOGY
//----------------------------------------------------------------------------
Type                    Edges       Multiple Edges Allowed?      Loop Allowed?
Simple Graph            Undirected  No                           No
Mutigraph               Undirected  Yes                          No
Pseudograph             Undirected  Yes                          Yes
Directed graph          Directed    No                           Yes
Directed multigraph     Directed    Yes                          Yes
//----------------------------------------------------------------------------

## Graph Terminology

### BASIC TERMINOLOGY

• Undirected Graph
--Two vertices $u$ and $v$ in $G$ are called adjacent or neighbors if $e=\left\{u,v\right\}$ is a edge of $G$.

--If $e=\left\{u,v\right\}$, the edge $e$ id called incident with $u$ and $v$. The edge $e$ is also said to connect $u$ and $v$. $u$ and $v$ endpoints.
--The degree of a vertex in an undirected graph is the number of the edges incident with it, except a loop at a vertex contribute twice to the degree of that vertex, denoted by $deg(v)$.
Isolated vertex: $deg=0$. Pendant vertex: $deg=1$.

Theorem:(The Handshaking Theorem) If $G$ is a graph with $m$ edges and n vertices $v_1,v_2,...,v_n$, then
$$\sum_{i=1}^{n}deg(v_i)=2m$$
In particular, the sum of all the degrees of all the vertices of the graph is even.
example: How many edges are there in a graph with 10 vertices each of degree 6?
solution: $|e|=30$.

• Directed Graph
--When $(u,v)$ is an edge of the graph $G$ with directed edges. $u$ is said to be adjacent to $v$ and $v$ is said wo be adjacent from $u$.

$u$--initial vertex , $v$--terminal or end vertex

The initial vertex and and terminal vertex of a loop are the same.

--The in-degree of a vertex $v$, denoted by $deg^-v$, is the number of edges with $v$ as their terminal vertex.
--The out-degree of a vertex $v$, denoted by $deg^+v$, is the number of edges with $v$ as their initial vertex.
(Note that a loop at a vertex contributes 1 to both the in-degree and the out-degree of this vertex.)
Theorem: Let $G=(V,E)$ be a graph with directed edges. Then
$$\sum_{i=1}^{n}deg^-(v_i)=\sum_{i=1}^{n}deg^+(v_i)=|E|$$

### SOME SPECIAL SIMPLE GRAPHS

1) Complete graph
The complete graph $K_n$ is the simple graph with n vertices and every pair of vertices is joined by an edge.
$K_n=(V,E),where E=\left\{\left\{u,v\right\}|u\neq v\right\}$
Remark: $|E|=C(n,2)$

2) Cycles
The cycle $C_n$, $(n\ge 3)$ consists of n vertices $v_1,v_2,...,v_n$ and edges $\left\{v_1,v_2\right\},\left\{v_2,v_3\right\},...,\left\{v_n-1,v_n\right\}$.

3) Wheels
We obtain the wheel $W_n$ when ew add an additional vertex to the cycle $C_n$, for $n\ge 3$, and connect this new vertex to each of the n vertices in $C_n$, by new edges.

4) $n$-Cubes
The $n$-Cubes, denoted by $Q_n$, is the graph that has vertices representing the the $2^n$ bit strings of length $n$.

5) Bipartite graph
A bipartite graph $G=(V,E)$ is a graph such that
$V=V_1\cup V_2$
,$V_1\cap V_2=\emptyset$
No edges exist between any two vertices in the same sub-set $V_k$, $k=1,2$.

example: $C_6$ is a Bipartite graph and $K_3$ is not bipartite.

Definition: A bipartite graph is the complete bipartite graph $K_{m,n}$ if every vertices in $V_1$ joined to a vertex in $V_2$ and conversely, $|V_1|=m,|V_2|=m$

### NEW GRAPH FROM OLD

Definition:$G=(V,E),H=(W,F)$

• $H$ is a subgraph of $G$, if $W\subseteq V,F\subseteq E$
• $H$ is a spanning subgraph of $G$, if $W=V,F\subseteq E$
• The union of two simple graph $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ is the simple graph with vertex set $V_1\cup V_2$ and edges set $E_1\cup E_2$. The union of $G_1$ and $G_2$ is denoted by $G_1\cup G_2$.

## Representing Graphs & Graph Isomorphism

There are many useful ways to represent graphs: Graph, adjacancy lists, adjacancy matrices and incidences.

Suppose that $G=(V,E)$ is a graph, where $|V|=n$. Suppose the vertices of G are listed arbitrarily $v_1,v_2,...,v_n$.

Definition: Let $G$ be a simple graph. The adjacency matrix $A={\lbrack a_{ij}\rbrack}_{n\times n}$ where $a_{ij}=$

$$\left\{ \begin{matrix} 1 & if\{v_i,v_j\}\in E \\ 0 & otherwise \end{matrix} \right.$$

Remark:
1) The adjacency matrix of a simple graph is symmetric, that is $a_{ij}=a_{ji}$.
2) $a_{ii}=0(i=1,2,...,n)$since a simple graph has no loops.
3) $deg(v_i)=\sum_{j=1}^na_{ij}$

Definition: Let G be an undirected graph with loops and multiple edges. The adjacency matrix $A=[a_{ij}]_{n\times n}$ where
$a_{ij}=$ the number of edges that are associated with $\{v_i,v_j\}$

Remark: The adjacency matrices of all undirected graphs, including multigraphs and psedographs are symmetric.

Definition: Let $G$ be a directed graph. The adjacency matrix $A=[A_{ij}]_{n\times n}$ where $a_{ij}=$

$$\left\{ \begin{matrix} 1 & if(v_i,v_j)\in E \\ 0 & otherwise \end{matrix} \right.$$

Remark:
1) The adjacency matrix of a directed graph does not have to be symmetric.
2) The adjacency matrix can also be used to describe a directed multigraph, where $a_{ij}=$ the number of edges that are associated to $(v_i,v_j)$.

• Incidence Matrix

Definition: Let $G=(V,E)$ be an undirected graph. Suppose that $v_1,v_2,...v_n$ are the vertices and $e_1,e_2,...,e_m$ are the edges. Then the incidence matrix with respect to this ordering of $V$ and $E$ is matrix $M=[m_{ij}]_{n\times m}$ where

$$m_{ij}= \left\{ \begin{matrix} 1 & {when\ edge\ e_i\ is\ incidence\ with\ v_i}\\ 0 & otherwise \end{matrix} \right.$$

Remark:
Incidence matrices can also be used to represent multiple edges and loops.
1) Mutiple edges $\Leftrightarrow$ columns with identicaL entries.
2) Loops $\Leftrightarrow$ columns with exactly entry equal to 1.

### ISOMORPHISM OF GRAPHS

Definition: Two simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are called isomorphic, if there is a bijection $f$ from $V_1$ to $V_2$ with the property
$$\forall a,b\in V_1,(a,b)\in E\Leftrightarrow(f(a),f(b))\in E_2$$
Bijection $f$ is called an isomorphism.

Remark:
1) It is difficult to determine whether two simple graphs are isomorphic.($n!$ possible bijection between two simple graphs with $n$ vertices)
2) We can show that two simple graphs are not isomorphic by showing that they not share the invariant properties under isomorphism, such as the same number of vertices, edges and the degrees of the vertices.
3) We can show that their adjacency matrices are the same, when the row and columns are labeled to correspond to the images under $f$ of vertices.

## Connectivity

### PATHS

Definition: A path of length $n(n\in Z^+)$ from $u$ to $v$ in an undirected graph is a sequence of edges $e_1,e_2,...,e_n$ of the graph such that
$$f(e_1)=\{x_0,x_1\},f(e_2)=\{x_1,x_2\},...,f(e_n)=\{x_{n-1},x_n\}$$
where $x_0=u$ and $x_n=v$.

• The path is a circuit if it begins and ends at the same vertex.
• A path or circuit is simple if it does not contain the same edge more than once.
• The graph is simple, we denote this path by its vertex sequence $x_0,x_1,...,x_n$.

Definition: A path of length $n(n\in Z^+)$ from $u$ to $v$ in a directed graph is a sequence of edges $e_1,e_2,...,e_n$ of the graph such that
$$f(e_1)=(x_0,x_1),f(e_2)=(x_1,x_2),...,f(e_n)=(x_{n-1},x_n)$$
where $x_0=u$ and $x_n=v$.

• The path is a circuit if it begins and ends at the same vertex.
• A path or circuit is simple if it does not contain the same edge more than once.

### CONNECTEDNESS IN UNDIRECTED GRAPHS

Definition:

• An undirected graph is called connected if there is a path between every pair of distinct vertices of the graphs.
• When a graph that is not connected is the union of two or more connected subgraphs -- are called the connected components.

Therem: There are a simple path between every pair of distinct vertices of a connected undirected graph.

Proof: Let $G=(V,E)$ be a connected undirected graph, $u,v\in V, u\neq v.$
$G$ connected $\Rightarrow \exists$ at least one path between $u$ and $v$. Let $u=x_0,x_1,...x_n=v$ be the vertex sequence of a path of least length.
Suppose it is not simple. Then $x_i=x_j$ for some $i$ and $j$ with $0\le i\le j$.
$\Rightarrow \exists$ a path from $u$ $v$ of shorter length with vertex sequence $x_0,...x_{i-1},x_j,...,x_n$ obtained by deleting the edges corresponding to the vertex sequence $x_i,...x_{j-1}$

Definition: The removal of a vertex and all edges incident with it produces a subgraph with more connected components than in the original graph. Such vertices are called cut vertices.
An edge whose removal produces a subgraph with more connected components than in the original graph is called a cut edge or bridge.

### CONNECTEDNESS IN DIRECTED GRAPHS

Definition:

• An directed graph is strongly connected if there is a path from $a$ to $b$ and from $b$ to $a$ when ever $a$ and $b$ are vertices in the graph.
• An directed graph is weakly connected if there is a path between any two vertices in the underluing undrected graph.

Remark: Strong connected $\Rightarrow$ Weakly connected

### COUNTING PATHS BETWEEN VERTICELS

Theorem: Let $G$ be a graph with adjacency matrix $A$ wwith respect to the ordering $v_1,v_2,...,v_n$. The number of different paths of length $r$ from $v_i$ to $v_j$, where $r$ is a positive integer, equals to the $(i,j)$th entry of $A^r$.

Proof: (By mathematical induction)
1) Let $G$ be a graph with adjacency matrix $A$ (Assuming an ordering $v_1,v_2,...,v_n$ of the vertices of $G$). The number of paths from $v_i$ to $v_j$ of length 1 is the $(i,j)$th entry of $A$.
2) Assume that the $(i,j)$th entry of $A^r$ is the number of different paths of length $r$ from $v_i$ to $v_j$.
$$A^{r+1}=A^rA$$
--the $(i,j)$th entry of $A^{r+1}$ equals
$$b_{i1}a_{1j}+b_{i2}a_{2j}+...+b_{in}a_{nj}$$
where $b_{ik}$ is the $(i,k)$th entry of $A^r$ ($b_{ik}$ is the number of paths of length r from $v_i$ to $v_j$).
A path of length $r+1$ from $v_i$ to $v_j$ is made up of a path of length r from $v_i$ to some intermediate vertex $v_k$, and an edge from $v_k$ to $v_j$.

$$\sum_{k=1}^n b_{ik}\cdot a_{kj}$$

these products are addred for all posiible intermediate vertices $v_k$, the desired result follows the sum rule for counting.
Remark: Theorem can be used to determine whether a graph is connected.

## Euler and Hamilton Paths

### EULER PATHS AND CIRCUITS

Definition: An Euler circuit in a graph $G$ is a simple circuit containing every edge of $G$. An Euler path is a simple apth containing every edge of $G$.
A graph $G$ is an $G$ is an Euler Graph if it has an Euler circuit.

Theorem: (Necessary and Sufficient Condition) A connected multigragh $G=(V,E)$ has an Euler circuit if and only if

• Every vertex in the graph havs even dege. (the $deg(v_i)$ must be even)

Proof: "$\Rightarrow$"
$G$ has a euler circle $\Rightarrow$ $G$ connected: trival
$G$ has a euler circle $\Rightarrow$ Every vertex in G has even degree

Consider $v\in V$. Suppose $v$ visites $k$ times by the Euler circuit, every visit use 2 new degree (in and out).
Hence,$deg(v_1)$ is even.
Proof: "$\Leftarrow$"
Take any $v_0\in V$.

• Consider any path $v_0\rightarrow v_1\rightarrow ... \rightarrow v_k \neq v_0$
$deg(v_k)$ is even

$v_k$ has an odd number of visited edges
$\Rightarrow v_k$ has an unvisited edge
Extend path $v_0\rightarrow v_1\rightarrow ... \rightarrow v_k \rightarrow v_{k+1}$
Repeat until $v_0\rightarrow v_1\rightarrow ... \rightarrow v_k \rightarrow v_m=v_0$

• Consider circuit $v_0\rightarrow v_1\rightarrow ... \rightarrow v_k \rightarrow v_m=v_0$
Suppose some $v_k$ has unvisited edge to $v_{m+1}$. By symmetry, let $v_k=v_0$

Extend path $v_0\rightarrow v_1\rightarrow ... \rightarrow v_k \rightarrow v_m=v_0\rightarrow v_{m+1}$
Repeat until $v_i$ has no unvisited edges.
$G$ connected $\Rightarrow$ all edges in $E$ visited
Therefore, $G$ has a Euler circuit.

Theorem: A connected multigraph $G=(V,E)$ has an Euler path but not an Euler circuit if and only if

• has exactly two vertices of odd degree

### HAMILTON PATHS AND CIRCUITS

Definition: A path $x_0,x_1,...,x_{n-1},x_n$ in the graph $G=(V,E)$ is called a Hamilton path if $V=\{ x_0,x_1,...x_{n-1},x_n\}$ and $x_i\neq x_j$
A circuit $x_0,x_1,..,x_{n-1},x_n,x_0$ (with $n>1$) in a graph $G=(V,E)$ is called a Hamilton circuit if $x_0,x_1,..,x_{n-1},x_n$ is a Hamilton path.
If a connected graph $G$ has a Hamiltonian circuit, $G$ is called a Hamilton graph.

Remark: A Hamilton circuit in a graph $G$ is a circuit which visited every vertex in $V$ exactly once.

Theorem: If $G$ is a connected simple graph with $n$ vertices where $n\geq 3$, then $G$ has a Hamilton circuit if the degree of each vertex is at least $n/2$.

Remark: The best algorithms known for finding Hamilton circuit in a graph or determing that no such circuit exists have exponential worst-case time complexity.

Responses
1. StevRing

Sildenafil Citrate Tablets generic viagra Cialis 5 Prezzo Meilleure Facon De Prendre Priligy

1. BookRora
@StevRing

http://northwestpharmaciescanadian.com - canadian pharmacy meds review how to find a doctor canadian pharmacy online no prescription health

2. Chisp
@StevRing

sertraline is the identify as a replacement for the treatment of erectile dysfunction. This generic hallucinogenic is very much noticeable in treating impotence. Tadalafil is the essential ingredient of medications. http://zoloftmedication.com what are the side effects of zoloft was oldest manufactured by means of Ranbaxy. This downer works on all men irrespective of any originator or duration of the quandary and the age. November 9, 2016 16:54

3. Appeptews
@StevRing

4. immizekax
@StevRing

Mild side effects of online canadian pharmacy are blur perspective, color blindness, acid upset stomach, hearing loss, diarrhea, pain in the neck, nasal congestion, urinary quarter infections, reddening of phizog, dizziness, etc. These are low-grade fallouts and disappear on own. Chiefly these symptoms materialize to men unique to this drug. Keep an eye on compelling the http://safemedsxl.com canadian pharmacy tied if they enter someone's head and as your body intention become traditional to it wish discontinue occurring at all. Yes, if these effects continue fit protracted in days of yore, then notify your doctor promptly. November 15, 2017 3:57

5. trifags
6. appoinc