Graph theory
Graph

In one restricted but very common sense of the term, a graph is an ordered pair G = (V, E) {\displaystyle G=(V,E)} comprising:

To avoid ambiguity, this type of object may be called precisely an undirected simple graph.

In the edge { x, y } {\displaystyle \{x,y\}}, the vertices x {\displaystyle x} and y {\displaystyle y} are called the endpoints of the edge. The edge is said to join x {\displaystyle x} and y {\displaystyle y} and to be incident on x {\displaystyle x} and on y {\displaystyle y}. A vertex may exist in a graph and not belong to an edge. Under this definition, multiple edges, in which two or more edges connect the same vertices, are not allowed.

In one more general sense of the term allowing multiple edges, a graph is an ordered triple G = (V, E, ϕ) {\displaystyle G=(V,E,\phi)} comprising:

To avoid ambiguity, this type of object may be called precisely an undirected multigraph.

A loop is an edge that joins a vertex to itself. Graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex x {\displaystyle x} to itself is the edge (for an undirected simple graph) or is incident on (for an undirected multigraph) { x, x } = { x } {\displaystyle \{x,x\}=\{x\}} which is not in { { x, y } ∣ x, y ∈ V and x ≠ y } {\displaystyle \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}. To allow loops, the definitions must be expanded. For undirected simple graphs, the definition of E {\displaystyle E} should be modified to E ⊆ { { x, y } ∣ x, y ∈ V } {\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\}}. For undirected multigraphs, the definition of ϕ {\displaystyle \phi } should be modified to ϕ: E → { { x, y } ∣ x, y ∈ V } {\displaystyle \phi:E\to \{\{x,y\}\mid x,y\in V\}}. To avoid ambiguity, these types of objects may be called undirected simple graph permitting loops and undirected multigraph permitting loops (sometimes also undirected pseudograph), respectively.

V {\displaystyle V} and E {\displaystyle E} are usually taken to be finite, and many of the well-known results are not true (or are rather different) for infinite graphs because many of the arguments fail in the infinite case. Moreover, V {\displaystyle V} is often assumed to be non-empty, but E {\displaystyle E} is allowed to be the empty set. The order of a graph is | V | {\displaystyle |V|}, its number of vertices. The size of a graph is | E | {\displaystyle |E|}, its number of edges. The degree or valency of a vertex is the number of edges that are incident to it, where a loop is counted twice. The degree of a graph is the maximum of the degrees of its vertices.

In an undirected simple graph of order n, the maximum degree of each vertex is n − 1 and the maximum size of the graph is n (n − 1) / 2.

The edges of an undirected simple graph permitting loops G {\displaystyle G} induce a symmetric homogeneous relation ∼ {\displaystyle \sim } on the vertices of G {\displaystyle G} that is called the adjacency relation of G {\displaystyle G}. Specifically, for each edge (x, y) {\displaystyle (x,y)}, its endpoints x {\displaystyle x} and y {\displaystyle y} are said to be adjacent to one another, which is denoted x ∼ y {\displaystyle x\sim y}.
startend:end_checker