Graph Theory

Order

the # of vertices in G

denoted: |V(G)|

Size

the # of edges in G

denoted: |E(G)|

Adjacent

vertices u,v \in V are _______ if they form an edge uv \in E

i.e. u & v are endpoints of an edge.

Incident

an edge e is ________ to v if v is an endpoint of e

Open neighborhood

the set of all vertices adjacent to v \in V

denoted: N(v) = {x \in V : vx \in E}

Open neighborhood of S \subset V

the union of all the neighborhood of vertices in S

degree of v \in V

the # of edges incident to v

degree sequence of graph order n

n-term sequence of the degrees of all vertices

walk

a sequence of vertices v1, v2, .., vk w/ v_iv_(i+1) \in E for i =1,…,k-1

path

if vertices are distinct in a walk

trail

if edges are distinct in a walk

length

the # of edges (including repeats) in a walk

cycle (or closed path)

a walk v1 … vk v1 w/ k >= 3 and v1 …. vk is a path

circuit (or closed trail)

a trail that starts and ends at the same vertex

complete graph

Kn, on n vertices if every pair of vertices is adjacent

empty graph

En on n vertices with no edges

Regular graph

G is _____ of degree k if every vertex has degree k

Cycle graph

Cn on n vertices (n >= 3)

Cn = (V, E)

V = {1,2,…, n}

E = { {i, i + 1} mod n} 1 =< i <= n