Two vertices are adjacent if they are connected by an edge.

A synonym for edge. See graph.

See cut vertices.

A graph is bipartite if its vertices can be partitioned into two disjoint subsets U and V such that each edge connects a vertex from U to one from V. A bipartite graph is a complete bipartite graph if every vertex in U is connected to every vertex in V. If U has n elements and V has m, then we denote the resulting complete bipartite graph by Kn,m. [..]

A circuit is a path which ends at the vertex it begins (so a loop is an circuit of length one).

A complete graph with n vertices (denoted Kn) is a graph with n vertices in which each vertex is connected to each of the others (with one edge between each pair of vertices). Here are the first five complete graphs:

See connected.

A graph is connected if there is a path connecting every pair of vertices. A graph that is not connected can be divided into connected components (disjoint connected subgraphs). For example, this graph is made of three connected components.

A cut vertex is a vertex that if removed (along with all edges incident with it) produces a graph with more connected components than the original graph. See connected.

The degree (or valence) of a vertex is the number of edge ends at that vertex. For example, in this graph all of the vertices have degree three. In a digraph (directed graph) the degree is usually divided into the in-degree and the out-degree (whose sum is the degree of the vertex in the underlying undirected graph).