Graph Theory

Graph

A nonempty set of connecting vertices and edges connecting vertices

Simple Graph

A graph with no loops and no multiple edges between the same pair of vertices (parallel edges)

Parallel Edges

Edges that have the same end vertices

Pendant Vertice (End Vertice)

A vertice with a degree of 1

Multigraph

A graph that may have multiple edges between the same pair of vertices

Loop

An edge of form (V,V), an edge that connects a vertex to itself

Degree

The number of edges with v as an end vertex. Denoted as d(v).

Adjacent Vertices

Vertices that are connected by an edge

Isolated Vertex

A vertex with a degree of 0

Complete Graph (Kn)

A simple graph where every pair of distinct vertices is connected by an edge.

Cycle Graph

A graph with degree of two for all vertices. Denoted by Cn, where n is vertices; n>=3

Wheel Graph (Wn)

Graph created when adding a vertex to the cycle graph Cn>=3 and connect that vertex to all vertices of Cn.

Path Graph (Pn)

A graph consisting of a sequence of vertices where each vertex is connected by an edge to the next. Denoted by Pn, where n is the number of vertices.

Bipartite

A simple graph whose vertex can be partitioned into two disjointed sets V1 & V2.

Complete Bipartite Graph (Km,n)

A bipartite graph where every vertex in V1 connects to every vertex in set V2.

Subgraph

A graph formed from a subset of vertices and edges of a graph

Induced Subgraph

A subgraph formed from a subset of vertices and all edges connecting them in the original graph

Connected Graph

A graph in which there is a path between every pair of vertices, meaning that all vertices are reachable from one another.

Disconnected Graph

A graph with at least one pair of vertices not connected by a path

Bridge (Cut-Edge)

An edge in a graph whose removal increases the number of connected components

Cut-Vertex

A vertex whose removal increases the number of connected components in a graph.

Walk

A finite sequence of vertices & edges in the Graph G(V,E) from an initial vertex to a terminal vertex

Cycle (Closed Path)

A walk that visits no vertex more than once except for the starting and ending vertex.

Trail

A walk with no repeated edges

Circuit

A closed trail

Path

A walk with no repeated vertices/edges