Graph Theory

Graph: a set of vertices and a set of edges that combine pairs of vertices together; represented with a capital letter.

G= (V, E)

Vertices: dots in a graph

Edge: the line between two vertices

Adjacent: two vertices that share an edge.

Incident:

• two edges with a common vertex are incident to one another.

• 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: is an edge that has the same vertex for both of its ends.

Walk in a graph: is a finite list of alternating vertices and

connecting edges that begins and ends with a vertex.

Path: is a walk with no repeated edges or vertices.

Cycle: is a walk that starts and ends at the same vertex and does not repeat edges or vertices.

Closed walk: is a walk that starts and ends with the same vertex.

Connected graph: at least one path connecting each pair of distinct vertices.

Disconnected graph: at least one pair of vertices that is not connected by a path.

Vertex cover: is a set of vertices 𝐴 so that every vertex

in the graph is either in 𝐴 or adjacent to a vertex in 𝐴.

When a vertex cover 𝐴 is as small as possible, 𝐴 is

called a minimum vertex cover.