undirected

Undirected describes a relationship or edge without inherent direction. In mathematics, a relation on a set is undirected if whenever a relates to b, b relates to a.

In graph theory, an undirected graph G consists of a set of vertices V and a set E of edges, where each edge is an unordered pair {u,v} of distinct vertices. There is no arrow or direction. Simple graphs disallow loops and multiple edges; more general undirected graphs may include parallel edges (multiedges) and loops.

Paths: In undirected graphs, a path is a sequence of vertices with consecutive vertices connected by edges; reachability is symmetric, so if there is a path from a to b, there is a path from b to a. The degree deg(v) is the number of incident edges; a loop contributes 2 to deg(v) in standard definitions.

Connectivity: A graph is connected when there is a path between every pair of vertices; otherwise it decomposes into connected components.

Matrices and algorithms: The adjacency matrix of an undirected graph is symmetric, reflecting the bidirectional nature of edges. Common algorithms such as BFS and DFS traverse undirected graphs to explore components, find paths, or test properties like connectivity or coloring.

Applications: Undirected graphs model many real-world structures where relations are mutual, such as social networks of friendships, road networks with two-way streets, and chemical graphs where bonds are undirected. The term undirected contrasts with directed or oriented graphs, where edges have a chosen direction, capturing asymmetric relations.