Graph Theory Definitions

These flashcards cover key definitions related to graph theory, including concepts such as vertices, edges, and types of graphs.

Graph

A finite set of points called vertices and line segments or curves called edges that start and end at vertices.

Loop

An edge that starts and ends at the same vertex.

Equivalent Graphs

Graphs having the same number of vertices connected to each other in the same way; the placement of the vertices and the shapes of the edges are unimportant.

Degree of a Vertex

The number of edges attached to a vertex; if a loop connects a vertex to itself, it contributes 2 to the degree.

Even Vertex

A vertex with an even number of edges attached to it.

Odd Vertex

A vertex with an odd number of edges attached to it.

Adjacent Vertices

Vertices that are connected by at least one edge.

Path

A sequence of adjacent vertices and the edges connecting them; vertices can appear more than once, but edges can only be part of a path once.

Circuit

A path that begins and ends at the same vertex; every circuit is a path, but not every path is a circuit.

Connected Graph

A graph in which there is at least one path connecting any two vertices.

Disconnected Graph

A graph that is not connected, made up of components that are connected by themselves.

Bridge

An edge that, if removed from a connected graph, would leave behind a disconnected graph.