7. Graph

1. Concept:

In general a graph G consists of two things:

1. The vertex set V , whose elements are called vertices, nodes or

points.

2. The edge set E or set of edges connecting pairs of vertices. If

the edges are directed then they are also called directed edges

or arcs. Each edge e 2 E is associated with a pair of vertices.

2. A graph with neither loops nor multiple edges is called a simple

graph. If a graph has multiple edges but no loops then it is called a

multigraph. If it has loops (and possible also multiple edges) then it is

called a pseudograph.

3.The Handshaking Theorem: Let G = (V,E) be an undirected graph

with e edges. Then 2e = ∑_vϵV▒〖deg⁡(v)〗

(This applies even if multiple edges and loops are present.)

3. Spencial graphs:

1. The n-cube: A graph with with 2n vertices labeled 0, 1, . . . , 2n − 1

so that two of them are connected with an edge if their binary representation

differs in exactly one bit.

2. Complete Graph: a simple undirected graph G such that every pair

of distinct vertices in G are connected by an edge

3. Bipartite Graph: a graph G = (V,E) in which V can be partitioned

into two subsets V1 and V2 so that each edge in G connects some vertex

in V1 to some vertex in V2.

4. Regular Graph: a simple graph whose vertices have all the same

degree.

4. Representations of Graphs:

1. Adjacency matrix. The adjacency matrix of a graph is a

matrix with rows and columns labeled by the vertices and such that

its entry in row i, column j, i 6= j, is the number of edges incident on i

and j

2. Incidence matrix. The incidence matrix of a graph G is a

matrix with rows labeled by vertices and columns labeled by edges, so

that entry for row v column e is 1 if e is incident on v, and 0 otherwise.

3. Graph Isomorphism. Two graphs G1 = (V1,E1), G2 =

(V2,E2), are called isomorphic if there is a bijection f : V1 ! V2 and a

bijection g : E1 ! E2 such that an edge e is adjacent to vertices v and

w if and only if g(e) is adjacent to f(v) and f(w)

5. Paths and circuits:

1. Paths. A path from v0 to vn of length n is a sequence of

n+1 vertices (vk) and n edges (ek) of the form v0, e1, v1, e2, v2, . . . , en, vn,

where each edge ek connects vk−1 with vk (and points from vk−1 to vk

if the edge is directed).

2. Connected Graphs. A graph G is called connected if there

is a path between any two distinct vertices of G. Otherwise the graph

is called disconnected.

3. Hamilton Circuits. A Hamilton circuit in a graph G is

a circuit that contains each vertex of G once (except for the starting

and ending vertex, which occurs twice). A Hamilton path in G is a

path (not a circuit) that contains each vertex of G once.

4. Dirac's Theorem. If G is a simple graph with n vertices with n _ 3

such that the degree of every vertex in G is at least n/2, then G has a

Hamilton circuit.

5. Ore's Theorem. If G is a simple graph with n vertices with n _ 3

such that deg(u) + deg(v) _ n for every pair of nonadjacent vertices u

and v in G, then G has a Hamilton circuit.

6. Gray Codes. A Gray code is a sequence s1, s2, . . . , s2n of n-binary

strings verifying the following conditions:

1. Every n-binary string appears somewhere in the sequence.

2. Two consecutive strings si and si+1 differ exactly in one bit.

3. s2n and s1 differ in exactly one bit.

6. Planar graphs:

1. Planar Graphs. A graph G is planar if it can be drawn

in the plane with its edges intersecting at their vertices only. One such

drawing is called an embedding of the graph in the plane.

2. Euler's Formula: Let G = (V,E) be a connected planar graph,

and let v = |V |, e = |E|, and r = number of regions in which

some given embedding of G divides the plane. Then:

v − e + r = 2 .

3. Let G = (V,E) be a simple connected planar graph with v

vertices, e _ 3 edges and r regions. Then 3r _ 2e and e _

3v − 6.

4. The graph K5 is non-planar. Proof: in K5 we have v = 5 and

e = 10, hence 3v − 6 = 9 < e = 10, which contradicts the

previous result.

5. The graph K3,3 is non-planar. Proof: in K3,3 we have v = 6 and

e = 9. If K3,3 were planar, from Euler's formula we would have

f = 5. On the other hand, each region is bounded by at least

four edges, so 4f _ 2e, i.e., 20 _ 18, which is a contradiction.

6. Kuratowski's Theorem: A graph is non-planar if and only if it

contains a subgraph that is homeomorphic to either K5 or K3,3.