Graph Theory

Undirected Graph

a graph without directed arrows

Directed graph

a graph with arrows

Pseudograph

are the most general type of undirected graphs since they may contain loops and multiple edges

Simple Graph

A graph without loops or multiple edges

Multigraph

A graph that may have multiple edges between the same vertices and possibly loops

Vertices

points in a graph

Adjacent Vertices

two vertices that are directly connected by an edge

Edges

the connections between pairs of vertices

Multiple Edges

two or more edges that connect the same pair of vertices

also known as parallel edges

Degree

The number of edges connected to a vertex

Paths

a sequence of edges that connect a sequence of vertices

Incident

describes the relationship between a vertex and an edge when the vertex is one of the endpoints of that edge

Complete Graph

contains exactly one edge between each pair of distinct vertices

Cycle

A path that starts and ends at the same vertex without repeating any edges or vertices except the starting/ending vertex

Wheel

a type of graph that consists of a cycle with an additional central vertex connected to all vertices in the cycle

Cube

a graph that represents the structure of an n-dimensional cube. Each vertex corresponds to a corner of the cube

Bipartite Graph

a type of graph where the vertices can be divided into two disjoint sets such that no vertices within the same set are adjacent

every edge connects to a vertex in one set to a vertex in the other set

Complete Bipartite Graph

Every vertex in one set is connected to exactly one vertex in the other set