Discrete Structures - Revised Graph Theory

Graph

collection of nonempty set of vertices and edges

end vertices

the two vertices at either end of an edge

parallel edges

edges with the same start and end vertices

loop

edges with the same start and end vertex

simple graph

a graph with no loops or parallel edges

empty graph

a graph with no edges

null graph

a graph with no vertices

trivial graph

a graph with only one vertex

adjacent edges

when an edge shares one or more vertice s

adjacent vertices

vertices connected by the same edge

degree

number of edges that are connected to a vertex (count loops twice)

pendent vertex

a vertex with degree of 1

pendent edge

a edge connected to a vertex with a degree of 1

isolated vertex

a vertex with degree 0

degree sequence

sequence of degrees in decreasing order

graphic

when a degree sequence forms a simple graph

complete graph

Kn, a graph where each vertex is adjacent to all the other vertices

Cycle Graph

a graph where n vertices, n >= 3, and each vertex has a degree of 2.

Wheel Graph

Wn, which is a cycle graph, but with an extra vertex that is adjacent to all the other vertices in the graph.

Bipartite Graph

A graph where its set of vertices can be divided into two sets, V1 and V2, and none of the vertices in V1 or V2 are adjacent within their own sets

Complete Bipartite Graph

A Bipartite Graph where each vertex is adjacent to every vertex from the other set and so on.

walk

a sequence of vertices and edges that allow us to travel from initial vertex to terminal vertex.

Trail

a walk with no repeated edges, but vertices can repeat.

path

walk with no repetition of vertices, and thus no repeating edges.

closed walk

a walk from initial vertex back to initial vertex,

circuit

a walk from initial vertex back to initial vertex with no repeating edges

cycle

a closed path or walk without repeating vertices or edges

length

total number of edges from initial vertex to terminal vertex

circuitless graph

a graph without any walks from initial vertex to initial vertex without repeating edges, or in other words without having a trail.

connected vertices

if a walk between two vertices exist

connected graph

when all the vertices of the graph have a walk between one another.

Euler walk

a walk that uses every edge only once e

Euler circuit

a closed walk, initial v to initial v, that uses each edge only once.

Euler Graph

a connected graph that has a closed walk, initial v to initial v, that uses each edge only once, aka Euler circuit

Hamiltonian Cycle

a circuit that uses every vertex in a graph exactly once

Hamiltonian Path

a path which uses every vertex once

Hamiltonian Graph

a graph with a path that uses each vertex once, aka with a Hamiltonian Path

Dirac’s Theorem

If every vertex, n>=3, has a degree >= n/2, graph must have a Hamiltonian cycle, which would mean it is a Hamiltonian Graph, which means that it has a Hamiltonian path.

Ore’s Theorem

if G is a simpel graph, n >= 3, and any two non-adjacent vertices degree sum >= n, G has a Hamiltonian circuit, thus is a Hamiltonian graph, thus has a Hamiltonian path.

tree

a connected graph with no circuits or cycles

trivial tree

a trivial graph, or a tree with only once vertex

forest

a disconnected graph, with each “piece” being at tree

rooted tree

a graph with one vertex that is designed as the root, and every edge points away from this root vertex.

level

the number of edges from it to the root on its unique path.

height

the maximum levels that are in the tree.

children

all the adjacent vertices below v

parent

the adjacent vertex that is above v

ancestors

all the vertices excluding the root and v itself, that are on the unique path from v to the root.

descendants

all the vertices below v that are connected

m-ary

every internal vertex has no more than m children

full m-ary

every internal vertex has exactly m children.

binary m-ary

if all leaves at level h or h-1

Decision Tree

a tree where every vertex corresponds to a decision/question, and edge is outcome, and then the leaves are the conclusion.