Graph Theory

Discrete Structures

Graph

A collection of vertices and edges.

Incident

Term used to describe the vertices that connect/border the edge.

Adjacent

Used when describing what vertices that share an edge are connected.

Isolated

Term used to describe a vertex that has no connecting/bordering edges.

Undirected Graph

A graph with the same number of vertices and edges, order does not matter.

Directed Graph

A graph with the same number of vertices and edges, order does matter.

Walk

A sequence of vertices and edges.

Closed Walk

A sequence of vertices and edges where the starting and ending vertex is the same.

Trail

A sequence of vertices and edges where there are no repeated edges.

Circuit

A sequence of vertices and edges where there are not only no repeated edges, but the starting and ending vertex are the same.

Path

A sequence of vertices and edges where there are no repeated vertices.

Cycle

A sequence of vertices and edges where there are not only no repeated vertices, but the starting and ending vertex are the same.

Connected Graph

A graph where every vertex is connected.

Disconnected Graph

A graph where every vertex is not connected.

Simple Graph

An undirected graph that has only one edge connecting vertices (no loops).

Spanning Subgraph

A subgraph that has the same number of vertices as the original graph with varying edges.

Induced Subgraph

A subgraph that takes a varying number of vertices from the original graph and has all adjacent edges.

Complete Graph

A graph denoted as Kn and is a loop-free undirected graph where every distinct pair of vertices is connected by a unique edge.

Isomorphic Graph

When two graphs have the same number of vertices and connected edges, but have different formats.

Bipartite Graph

A graph where its vertex set can be partitioned into two independent sets. This means all edges in the graph run between the set A to set B, and there are no edges whose both endpoints lie in the same set.

Complete Bipartite Graph

A graph where its vertex set can be partitioned into two independent sets. This means all edges in the graph run between the set A to set B, and there are no edges whose both endpoints lie in the same set. The vertices from set A must individually connected with every vertex in set B.

Euler Path

A sequence of vertices and edges where every edge is used exactly once.

Euler Cycle

A sequence of vertices and edges where every edge is used exactly once and the starting and ending vertices are the same.

Hamiltonian Path

A sequence of vertices and edges where every vertex is used exactly once.

Hamiltonian Cycle

A sequence of vertices and edges where every vertex is used exactly once and the starting and ending vertices are the same.