Graph Theory

Graph

A non-empty set of vertices and edges.

G: (V,E)

Denotation of a graph G's vertices and edges.

Set of Vertices

V = {v1, v2, v3, …, vn}

Set of Edges

E = {e1, e2, e3, …, en}

End Vertices

Two vertices on the border of any edge.

Parallel

Edges that have the same end vertices.

Loop

An edge in the form (v, v).

Simple Graph

A graph without any parallel edges or loops.

Empty Graph

Graph with no edges.

Null Graph

Graph with no vertices.

Trivial

Graph with only one vertex.

Adjacent Edges

Edges that share a common end vertex.

Adjacent Vertices

When two vertices are connected by an edge.

Degree of a Vertex

Written as d(v), it represents the number of edges with v as an end vertex. By convention a loop is counted twice.

Pendant Vertex

A vertex with degree 1.

Pendant Edge

Edge that has a pendant vertex as an end point.

Isolated Vertex

Vertex with degree 0.

Minimum Degree

Denoted as δ(G)

Max Degree

Denoted as Δ(G)

Handshaking Theorem

The sum of all vertex degrees in a graph equals twice the number of edges.

Adjacent Vertices (neighbors)

Vertices that are connected by an edge.

Incident

The edge between two vertices.

Neighborbood

A set of vertices that consists of all vertices that are connected to it by edges.

Adjacent to

When a vertex points at another.

Adjacent from

When a vertex is pointed at by another.

Initial Vertex

First vertex in a directed graph.

Terminal/end vertex

Second vertex in a directed graph.

In-degree

How many edges point to that vertex.

Out-degree

How many edges point out of that vertex.

Complete Graph

Simple graph that contains exactly one edge connected to every vertex.

Cycle

A graph with at least three vertices that start and end at the same vertex and does not have repeating vertices.

Wheel

A graph that start and end at the same vertex and does not have repeating vertices, while having a vertex in the middle that connects to all other vertices.

Bipartite Graph

An undirected graph whose vertices can be divided into two disjoint independent sets, say U and V, such that every edge connects a vertex in U to a vertex in V and that there are no edges within U or within V.

Complete Bipartite Graph

A graph denoted K{m,n}, where two partite sets have sizes m and n, and every possible edge between the two sets connect.