Graph Theory

Graph

A set of vertices and a set of edges that combine pairs of vertices together, represented as G = (V, E).

Vertices

Dots in a graph.

Edge

The line between two vertices.

Adjacent

Two vertices that share an edge.

Incident

Two edges are incident if they have a common vertex; two vertices are incident if they are ends of the same edge.

Degree

The degree of a vertex denoted as d(u), is the number of edges that meet at that vertex.

Loop

An edge that has the same vertex for both of its ends.

Walk in a graph

A finite list of alternating vertices and connecting edges that begins and ends with a vertex.

Path

A walk with no repeated edges or vertices.

Cycle

A walk that starts and ends at the same vertex and does not repeat edges or vertices.

Closed walk

A walk that starts and ends with the same vertex.

Connected graph

A graph with at least one path connecting each pair of distinct vertices.

Disconnected graph

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

Vertex cover

A set of vertices A so that every vertex in the graph is either in A or adjacent to a vertex in A.

Minimum vertex cover

A vertex cover A that is as small as possible.