Graph Theory Vocabulary

Edge

Line joining a pair of nodes.

Loop

Is an edge or arc that joins a vertex to itself.

Vertex

Is a point or a circle. It is the fundamental unit from which graphs are made. (Sometimes called a node)

Degree of a Vertex

The number of edges that connect to the vertex. (Loops count twice)

Walk

A series of vertices and edges.

Closed Walk

Is a walk from a vertex back to itself; a series of vertices and edges which begins and ends at the same place.

Circuit

A closed walk with every edge distinct.

Cycle

Is a closed walk with no repeated vertices. (Except that the first and last vertices are the same)

Path

Is a walk with no repeated vertices.

Tree

A connected graph with no cycles.

Node

A synonym for vertex.

Arc

A synonym for edge.

Graph

A set of vertices (or nodes), together with a set of edges (or arcs).

Trail

A walk in which no edge is repeated.