Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures.
Graph
A general example of a graph with three vertices and six edges.
A graph or undirected graph G is an ordered pair G: = (V,E) that is subject to the following conditions:
-
- V is a set, whose elements are called vertices or nodes,
- E is a multiset of unordered pairs of vertices (not necessarily distinct), called edges or lines.
(Note that this defines the most general type of graph. Some authors call this a multigraph and reserve the term "graph" for simple graphs.)
The vertices belonging to an edge are called the ends, endpoints, or end vertices of the edge.
V (and hence 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. The order of a graph is | V | (the number of vertices). A graph's size is | E | , the number of edges. The degree of a vertex is the number of edges that connect to it, where an edge that connects to the vertex at both ends (a loop) is counted twice.
The edges E induce a symmetric binary relation ~ on V which is called the adjacency relation of G. Specifically, for each edge {u,v} the vertices u and v are said to be adjacent to one another, which is denoted u ~ v.
For an edge {
u,
v}, graph theorists usually use the somewhat shorter notation
uv.
Posts
