discrete ii graph theory

End vertices

Name for vertices which are connected by an edge

Parallel Edges

Edges with same end vertices.

Simple

Graphs with no edges or loops

Empty

Graph with no edges

Null graph

Graph with no vertices

Trivial

Graph with one edge

Adjacent

Connected by an edge

Degree/D(v)

num of edges with v as end vertex. Count loops twice

Pendant

Vertex with degree 1

Pendant edge

Edge with a pendant vertex as an end point

Isolated vertex

Vertex with degree 0

Complete Graph

Written as Kn. N is num of vertices. Contains all possible edges between every pair of veritces

Cycle Graph

Cn, n is num of vertices. The edges go in a circle type of shape. All vertices have n-1 edges

Wheel Graph

Similar to a cycle but there’s a vertex in the middle. All vertices have degree of N

Bipartite Graph

A graph where if Vi can be partitioned into two disjoined sets V1 and V2 and

V = V1 U V2

All edges connect from V1 to V2.

complete bipartite graph

Every vertex of one set is connected to every vertex in other set. K m,n

Subgraph

A graph where Vi is a subset of V and Ei is a subset of E

Walk

Finite sequence of edges and vertices.

Initial Vertex

Beginning of walk

Terminal Vertex

End of walk

Cycle

A walk where the initial and terminal vertices are the same

Trail

Walk with no repeated edges

Path

Walk with no repeated vertices and edges except for initial and terminal vertices

Circuit

Path which has the same initial and terminal vertex

Euler Circuit

Walk that has the same initial and closed vertex which uses each edge once. All vertices must have even degree

Euler Walk

Walk that uses each edge once. Exactly two vertices have odd degree

Hamilton Circuit

Circuit that uses every vertex in a graph exactly once. Two non adjacent vertices W and X must have degrees such that

D(W) + D(X) > n

Hamilton Path

Path which uses every vertex in a graph once. Two non adjacent vertices W and X must have degrees such that

D(W) + D(X) > n -1

Euler Graph

Connected graph with a Euler circuit

Tree

A connected undirected simple graph. Simple unique path between all vertices.

Rooted Tree

A type of tree in which there is one “root” vertex and all other edges come from the root.

Leaf

A vertex of a rooted tree with no children

Internal vertices

Vertices with children

m-ary tree

All internal vertices have no more than m children

full m-ary tree

Each internal vertex has m children

binary tree

full m-ary tree with m=2

Forest

A graph made of multiple trees