Graph Theory Definitions and Concepts

End vertices

Two vertices v1 and v2 of edge e1 = (v1,v2)

Parallel Edges

Edges with the same end vertices

Loop

An edge connecting a vertex to itself (vk,vk)

Simple Graph

A graph without parallel edges or loops

Empty Graph

A graph with no edges

Null Graph

A graph with no vertices

Trivial Graph

A graph with only one vertex

Adjacent Edges

Edges with a common end vertex

Adjacent Vertices

Vertices connected by an edge

Degree of a vertex d(v) or deg(v)

(special case too)

Total number of edges that have that vertex as an end vertex (loops counted twice)

Pendant Vertex

A vertex with degree 1

Pendant Edge

An edge that is connected to a pendant vertex (vertex with degree 1)

Isolated vertex

Vertex with degree 0

Δ(G)

Max degree in graph

δ(G)

Min degree in graph

Theorem to find total # of edges from degrees

Let G = (V,E) be an undirected graph with m edges. Then 2m = ∑deg(V). Even if multiple edges and loops present.

Theorem (maximum degree)

With a simple graph with n vertices, the maximum degree is n-1, as there's n-1 vertices for any single vertex to connect to.

Theorem (δ(G) calculation)

δ(G) can be found by seeing how many max-degree vertices you have.

Subgraph of G

(V,E), is Gi: (Vi, Ei), if and only if Vi ⊆ V, Ei ⊆ E. Ie each edge in Gi has the same adjacent vertices as in G.

Complete Graph (Kn)

(also give degree sequence)

Denoted by Kn, n = # of vertices. A simple graph in which every vertex is adjacent to all other vertices. All possible edges included in the graph. Each vertex degree is n-1. Degree sequence: n-1, n-1, n-1,...,n-1 (n times).

Cycle graph (Cn)

(also give degree sequence)

Denoted by Cn, n = # of vertices, n >= 3. Graph with degree sequence 2 for all vertices. And only includes edges {(v1,v2), (v2,v3),...,(vn-1,vn), (vn,v1)}. Degree sequence: 2,2,2...,2 (n times).

Wheel graph (Wn)

(also give degree sequence)

Denoted by Wn, n = # of vertices excluding the extra vertex added. Add one vertex to the cycle graph Cn (n>=3). Connect that vertex to all other vertices. Degree sequence: n, (then) 3,3,...,3 (n times).

Complimentary graph (G̅)

Denoted by G̅. Same vertices as G. Consists only of all the possible edges that don't exist in G. G∪G̅ should be a complete graph. K̅n = empty graph with n vertices.

Bipartite Graph

A simple graph G: (V,E) where you can partition V into two nonempty disjoint sets V1, V2, such that V1∪V2 = V. And every edge connects a vertex in V1 to a vertex in V2. No two v1 vertices, and no two v2 vertices, can be adjacent by themselves.

Walk

Sequence of vertices and edges that helps us travel between two vertices in a graph

(Can repeat edges/vertices)

(Initial and terminal vertices can be the same)

Path

A walk with no repetition of vertices

(except for initial and terminal vertices)

Connected vertices

Two vertices are connected if there is a u•v walk between them (and vice versa)

Complete Bipartite Graph

(also give degree sequence)

Denoted by Km,n

With m vertices in set V1, and n vertices in set v2

Bipartite graph that contains every possible edge from v1 to v2 vertices and vice versa

Degrees in Complete Bipartite

With Km,n

For vertices in the v1 (m) set, the degree is n

For vertices in the v2 (n) set, the degree is m

How tell if graph is bipartite (coloring method)

1. Start at random vertex

2. Find adjacent vertex and assign a different color

3. Repeat step 2 alternating between the two colors until all vertices colored

If:

Every pair of adjacent vertices has a different color, it's bipartite

Else:

Not bipartite

Issue with coloring method

Slow time run

Initial Vertex

Starting vertex in a walk

Terminal vertex

Ending vertex in a walk

Trail

A walk with no repeated edges

(vertices can still repeat)

Theorem: Relationship between Path and Trails

Path implies Trail

If you want to repeat an edge, you need to return to a vertex you've been to already

Closed Walk

Walk from a vertex to itself

Circuit

Closed trail

Cycle

Closed path

Length of Walk

total # of edges you go over to get to terminal vertex

Circleless Graph

(and how to know if it's one)

Graph with no circuits

Any graph is circleless if:

-No loops

-At most one path to travel between any pair of vertices

Theorem: How to tell if graph is bipartite (cycle length)

A given simple graph is bipartite if and only if it does not have an odd-length cycle

For what values of N wiill Kn be bipartite?

Only n=2

-Any other n value > 2 can find an odd-length cycle (triangle)

-n=1 doesn't work because can not partition a single vertex into two sets

For what values of N wiill Cn be bipartite?

When n is even

n odd can't work b/c odd length cycle

Regular Graph / n-regular

Regular: Each vertex of graph has same degree

n-regular: Each vertex of graph has degree n

u•v walk

A walk starting at u and ending at v

Connected Graph

(also status of trivial)

A graph where all vertices are connected (a walk exists between every pair of vertices)

(Trivial graph counts as connected)

Cut vertex

A single vertex in a connected graph whose removal increases the # of connected components in a graph

Cut edge

A single edge whose removal increases the # of connected components in the graph

Euler Walk

A walk that uses each edge exactly once

(EXPLICITLY NOT CLOSED IF WE JUST SAY EULER WALK)

Euler circuit

Closed Euler walk

(closed walk that uses each edge exactly once)

Euler graph

A connected graph that has a Euler circuit

Theorem for Euler walk

A connected graph G has a Euler walk if and only if it has exactly 2 vertices with an odd degree

Theorem for Euler circuit

A connected graph has a Euler circuit if and only if all vertices in graph have an even degree

Hamiltonian Circuit/Cycle

(both terms mean the same thing atp)

A circuit that uses every vertex in a graph exactly once

Hamiltonian Path

A path that uses every vertex in a graph exactly once

Hamiltonian Graph

A graph that contains a Hamiltonian circuit

Theorem relating Hamiltonian circuits and Hamiltonian paths

If a graph has a Hamiltonian circuit, it also has a Hamiltonian path

(but not vice versa)

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 Hamiltonian circuit

(If not, still possible to have Hamiltonian circuit)

Ore's Theorem

If:

- G is a simple graph with n vertices with n>=3 such that d(u)+d(v) >= n for every pair of nonadjacent vertices u and v in G

Then:

- G has a Hamiltonian circuit

(If not, still possible to have Hamiltonian circuit)

Theorem (unofficial): Hamiltonian Circuits & Cut Vertices

If Graph G contains a cut vertex or cut edge, then it cannot contain a Hamiltonian cycle

(

-Travelling over a cut vertex essentially removes it from the graph for your cycle.

-However, you need to travel over the cut vertex to return to the initial vertex because Hamiltonian cycles are closed,

-and you can't avoid it because Hamiltonian must use every vertex.

-Therefore, a Hamiltonian cycle can't exist with a cut vertex

)

Tree

Connected simple undirected graph with no simple circuits

Theorem: Trees & paths

An undirected graph is a tree if and only if there is a unique simple path between any two vertices

Trivial Tree

Tree with only one vertex

Forest

A graph that's circuit free and not connected

OR ALSO

A disconnected graph where each of it's components are trees

Rooted Tree

A tree in which one vertex is root, and all other edges are away from root

(root on top, most important)

Level

Number of edges along the unique path between vertex in tree and the root

Height

Max level of any vertex in tree

Children of a vertex

Vertices adjacent to v and one level farther away from the root than v

Parent of a vertex

Adjacent to the vertex and one level closer to the root than v

Internal vertices

Vertices with children

Leaf vertices

Vertices without children

Siblings

Two distinct vertices that are both children of the same parent

Ancestor

Any vertex between a vertex (other than root) and root on path

(root always ancestor)

Descendent

The descendants of a vertex v are those vertices that have v as an ancestor

OR

A descendent of vertex v is any vertex w whose path from the root contains v

Theorem (# of leaves)

If an m-ary tree of height h has L leaves, then h >= [log_m(L)].

If the m-ary tree is full and balanced, h = [log_m(L)]

Theorem (given on exam)

A full m-ary tree with

(i ) n vertices has i = (n − 1)/m internal vertices and l = [(m − 1)n + 1]/m leaves,

(ii ) i internal vertices has n = mi + 1 vertices and l = (m − 1)i + 1 leaves,

(iii ) l leaves has n = (ml − 1)/(m − 1) vertices and i = (l − 1)/(m − 1) internal vertices.

n: total vertices

i: internal vertices

L: leaves

M: # of children for internal vertices

Theorem (trees and m-ary)

Every rooted tree is a m-ary tree

(but not necessary full m-ary)

Theorem (tree and edges)

A tree with n vertices has n-1 edges

Binary tree

m-ary tree with m=2

Balanced tree

Rooted m-ary tree of height h where all leaves are at levels h or h-1

Decision Tree

Flow chart structure of rooted tree

-Branches = outcomes of test

-Internal vertices = Intermediate decisions

-Leaves = conclusion, decision, evaluation

Must be optimal (least tasks needed to get result)