Graph

Graph

A graph(or undirected graph) G consists of a set V of vertices(or nodes) and a set E of edges(or arcs) such that each edge e∈E is associated with an unordered pair of vertices.

G = (V , E)

A simple graph is a graph without loops or parallel edges.

Subgraph

Let G = (V, E) be a graph, we call (V', E') a subgraph of G if

(a) V'⊆V

(b) E'⊆E such that for every edge e'∈E', if e' is incident on v' and w', then v',w'∈V'.

---

Degree

The degree of a vertex v, denoted by δ(v), is the number of edges incident on v.

Theorems

if G is a graph with n vertices and m edges, then

sum(δ(vi))[i=1~n] = 2m

Path

A path from vo to vn of length n is an alternation sequence of n+1 vertices and n edges beginning with vertex vo and ending with vertex vn,

(vo, e1, v1, e2, v2, ..., vn-1, en, vn),

in which edge ei is incident on vertices vi-1 and vi for i = 1, ..., n

A simple path from v to w is a path from v to w with no repeated vertices.

Theorems

A graph has a path with no repeated edges from v to w(v≠w) containing all the edges and all vertices if and only if it is connected and v and w are the only vertices having odd degrees.

Cycle

A cycle(or circuit) is a path of nonzero length from v to v with no repeated edges.

A simple cycle is a cycle from v to v in which, except for the beginning and ending vertices that are both equal to v, there are no repeated vertices.

Theorems

If a graph G contains a cycle from v to v, G contains a simple cycle from v to v

---

connected

The connected graph is the graph in which for any vertices v and w in G, there is a path from v to w.

Complete 

The complete graph on n vertices, denoted Kn, is the simple graph with n vertices in which there is an edge between every pair of distinct vertices.

Bipartite

The bipartite graph is the graph whose vertex set V is partitioned into sets V1 and V2 such that V1∩V2 = Φ, V1∪V2 = V, and each edge in E is incident on one vertex in V1 and one vertex in V2.

The complete bipartite graph on m and n vertices, denoted Km,n, is the simple graph whose vertex set is partitioned into sets V1 with m vertices and V2 with n vertices, and the edge set consists of all edges of the form (v1, v2) with v1∈V1, and v2∈V2.