Introduction

Definitions

Theorems

Theorem 1.6:                    If a graph G contains a u-v walk of length l, then G contains a u-v path of length at most l

Graphs and Graph Models

A graph G consists of a finite non-empty set V of objects called vertices. (singular: vertex)
A set E of 2-element subsets of V called edges. The sets V and E are the vertex set and the edge set of G respectively. Graph G is a ordered pair of sets V and E. ( G = (V, E) )
Vertices can also be called points or nodes, edges lines.
Two graphs G and H are equal if V(G) = V(H) and E(G) = E(H), written as G = H.

Example:

V (G) = { a, b, c }
E (G) = { {ab},{ac},{bc} }

A 2-element set {u, v} can be written as uv (or vu).
The following statements can be made ifs uv is an edge of G called e:

1. u and v are said to be adjacent ( or called neighbors ) in G.
2. The vertex u and the edge e are said to be incident with each other.  (same for v and e)
3. u and v are joined by edge e.

If distinct edges incident with a common vertex, they are called adjacent edges.
Number of vertices in G is called the order of G ( or n ), the number of edges the size of G ( or m ).
A graph with order = 1 is called a trivial graph.
A graph with order >= 2 is called a nontrivial graph.

A graph without labels is called an unlabeled graph, a graph with labels is called a labeled graph.

Connected Graphs

A graph H is called a subgraph of graph G, written H ⊆ G, if  V(H) ⊆ V(G) and E(H) ⊆ E(G). G contains H as a subgraph.
If H ⊆ G and V(H) is proper subset of V(G) or E(H) of E(G), then H is a proper subgraph of G.
If a subgraph of graph G has the same vertex set as G, then it is a spanning subgraph of G.

A subgraph F of a graph G is called an induced subgraph of G if whenever u and v are vertices of F and uv is an edge of G, then uv is an edge of F as well.
If S is a non-empty set of vertices of a graph G, then the subgraph of G induced by S is the induced subgraph with the vertex set S. Denoted by 〈S〉_G.
(The subgraph contains only the edges of G for which the vertices exist in F)

For a nonempty set X of edges, the subgraph 〈X〉 induced by X has edge set X and consists of all vertices that are incident with at least one edge in X.
This subgraph is called an edge-induced subgraph. (The subgraph contains all vertices of X that are connected to a edge in edge set of X)

A u - v walk W in G is a sequence of vertices in G, beginning with u and ending at v such that consecutive vertices in the sequence are adjacent.

W : u = v₀, v₁, ... , v_k = v,
where k ≥ 0 and v_i and v_i+1 adjacent for i = 0, 1, ... , k-1
Each vertex v_i (0 ≤ i ≤ k), each edge v_iv_i+1 (0 ≤ i ≤ k-1) lies or belongs to W.

Listed vertices are not distinct, however consecutive vertices in W are distinct since they are adjacent.
If u = v, then the walk W is closed; while if u ≠ v, then W is open.
The number of edges encountered in a walk is called the length of the walk. Thus the length is defined as k in v_k
A walk with a length of 0 is a trivial walk, so W : v is a trivial walk.
A u - v trail is a u - v walk in which no edge is traversed more than once. (Although vertices may be visited more than once)
A u - v path is a u - v trail in which no vertex is traversed more than once.

Theorem: If a graph G contains a u-v walk of length l, then G contains a u-v path of length at most l.

A circuit in a graph G is a closed trail of length 3 or more.
A circuit that repeats no vertex, except for the first and the last, is a cycle.
A k-cycle is a cycle of length k. A 3-cycle is also referred to as a triangle.
A cycle with odd length is called an odd cycle, even length an even cycle.
The subgraph of G formed by the trail, path, circuit or cycle is called a trail, path, circuit or cycle.

If G contains a u - v path, then u and v are said to be connected, and u is connected to v. (Although not necessarily joined; an edge between them)
Graph G is connected if every two vertices of G are connected. (A trivial graph is connected)
A not connected graph is called disconnected.
A connected subgraph of G that is not a proper subgraph of any other connected subgraph of G is a component of G. (A connected graph has only 1 component)

Theorem:    Let R be the relation defined on the vertex set of a graph G by  u R v,  where u, v ∊ V(G).
                   If u is connected to v, that is, if G contains a u - v path.
                   Then R is an equivalence relation.

Each vertex and each edge of a graph G belong to exactly one component of G.
This implies that if G is a disconnected graph and u and v are vertices belonging to different components of G,
then uv∉E(G)
(So there is no edge between u and v if u and v belong to different components)

Theorem:    Let G be graph of order 3 or more.
                   If G contains two distinct vertices u and v such that G - u and G - v are connected,
                   then G itself is connected.

The distance between u and v is the smallest lengthof any u - v path in G and is denoted byd_G(u,v), or simply d(u,v).
Hence if d(u, v) = k, then there exists a u - v path. Thus:  P : u = v₀, v₁, ... , v_k = v
A u - v path of length d(u, v) is called a u - v geodesic.
In general, 0 ≤ d(u, v) ≤ n-1 for every two vertices u and v (distinct or not) in a connected graph of order n.

The diameter of G is the greatest distancebetween any two vertices of a connected graph G, denoted by diam(G).

Theorem:    If G is a connected graph of order 3 or more,
                   then G contains two distinct vertices u and v such that G - u and G - v are connected.

Theorem:    Let G be a graph of order 3 or more.
                   Then G is connected if and only if G contains two distinct vertices u and v such that G - u and G - v are connected.

Common Classes of Graphs  

A path of length n is denoted as P_n, a cycle of length is denoted as C_n.
A graph G is complete if every two distinct vertices of G are adjacent.
A complete graph of order n is denoted by K_n. K_n has the maximum possible size for a graph with n vertices.
The number of pairs of vertices in K_n is

<Img 1.22, p 20>

Theorem: If G is a disconnected graph, then G is connected.

Theorem: A nontrivial graph G is a bipartite graph if and only if  contains no odd cycles.