Due to the vast breadth of the usefulness of
graphs, the terminology varies widely, not only from one graph variety to
another, but also from one application to another. The table in Fact 1 gives
synonyms for several terms.
Definitions:
A vertex is usually conceptualized as a point. Abstractly, it is a member of the
first of two sets that form a graph.
An edge is usually conceptualized as a line, either joining one vertex to
another or joining a vertex to itself. Abstractly, it
is a member of the second of two sets that form a graph.
A proper edge (or link) is an edge that joins one vertex to another.
A loop (or self-loop)
is an edge joining a vertex to itself.
The endpoints of an edge are the
vertices that it joins. A loop has only one endpoint.
An incidence rule specifies the
endpoints of every edge.
An edge e
is incident with a vertex v if v is an endpoint of e.
A graph is a set V of vertices and a set E of edges (both sets finite unless declared otherwise)
such that all the endpoints of edges in E
are contained in V .
It is often denoted G = (V,E), or (VG,EG),or (V (G),E(G)). Sometimes, each
edge is regarded as a pair of vertices.
An isolated point of a graph G = (V,E) is a vertex in V that is not the endpoint of any edge in E.
Vertices u
and v are adjacent if there is an edge whose endpoints are u and v.
Two edges are adjacent if they
have a common endpoint.
A neighbor
of a vertex is any vertex to which it is adjacent.
An attribute of the edge-set or
vertex-set is a feature such as length, cost, or color
sometimes attached to graphs.
A graph model is a graph which
(quite frequently, in applications) may have additional attributes on its edges
and/or vertices. The vertices and edges of the model may represent arbitrary
objects and relationships from the context of the application.
A weighted graph is a graph model
in which each edge is assigned a number called the weight or the cost.
A node is sometimes a synonym for
a vertex and sometimes refers to whatever is modeled
by a vertex in a graph model.
A line is sometimes a synonym for
an edge and sometimes refers to whatever is modelled by an edge in a graph
model.
A multi-edge in an undirected
graph is a set of more than one edge with the same endpoints, and in a digraph
a set of more than one edge such that each edge in the set has the same head
and each edge in the set has the same tail. A graph with a multi-edge is also
said to have multiple edges or parallel edges.
A multi-edge of multiplicity n is
a set of n edges with the
same endpoints.
A set of parallel edges is a set
of edges with the same endpoints, i.e., a multi-edge. A pair of anti-parallel
arcs is a pair of oppositely directed arcs between the same two endpoints.
A graph is simple if it has no
loops or multi-edges. Topologists often say simplicial,
because such a graph is a special case of a “simplicial
complex”.
A multi-graph is another name for
a graph with multi-edges but no self-loops, used for emphasis when the context
is largely restricted to simple graphs.
A pseudo-graph (or general
graph) is another name for a graph in which loops and multi-edges are
permitted, used for emphasis when the context is largely restricted to loopless graphs.
A direction on an edge is an
ordering for its endpoints so that the edge goes from one endpoint and to
the other. Any edge, including a self-loop, can be directed by giving it a
sense of forward progression, e.g., in a graph drawing, by placing an arrowhead
to show which way is forward, or by ordering the endpoints.
An arc is another name for a
directed edge.
The tail of an arc is the vertex
at which the arc originates.
The head of an arc is the vertex
at which the arc terminates.
A directed graph or digraph is
a graph in which every edge is directed.
A strict digraph has no self-loops
and no pair of arcs with the same tail and head.
The degree of vertex v, deg(v),is the number
of proper edges plus twice the number of loops incident with v. Thus, in a drawing, it is the number of
edge-endings at v.
The valence of a vertex is a
synonym for degree adapted from terminology in chemistry.
The degree sequence of a graph is
the sequence of the degrees of its vertices, most often sorted into size order,
ascending or descending.
A regular graph is a graph such that
all vertices have the same degree. It is called
k-regular if the vertices all have degree k.
A graphical sequence is a sequence
of nonnegative integers that is the degree sequence of some simple graph.
The number of vertices of a graph is sometimes
called the order.
The number of edges of a graph is sometimes
called the size.
The empty graph is the graph whose
vertex set and edge set are both empty. This is
also called the null graph (and is sometimes not considered to
be a graph).
The trivial graph is the graph
with one vertex and no edges.
Facts:
1. The following table gives lists of some synonymous graph theory terms:
vertex: point, node
edge: line
loop: self-loop
neighbor:
adjacent vertex
arc: directed edge
degree: valence
number of vertices: order
number of edges: size
nonsimple
graph: pseudograph, general graph
loopless
nonsimple graph: multi-graph
empty graph: null graph
2. The following table lists the varieties of graphs:
graph variety loops allowed? multi-edges
allowed?
digraph YES YES
general graph YES YES
multi-graph NO YES
pseudo-graph YES YES
simple graph NO NO
strict digraph NO NO*
*at most one arc in each direction between two
vertices.
3. In a drawing of a graph,
the degree of a vertex v equals the number of edge-ends at v.
The degree of v
need not equal the number of edges at v, since each loop contributes both its ends toward the degree.
4. Euler’s theorem:
In every graph, the sum of the degrees equals twice the number of edges. From this result it follows
that in all graphs the sum of the degrees of all vertices is even.
5. In every graph the
number of vertices of odd degree is even.
6. The name handshaking lemma is commonly applied to various elementary results about the degrees of
simple graphs, especially Facts 4 and 5.
7. In every simple graph
with at least two vertices, there is a pair of vertices with the same degree.
8. Havel’s theorem: A sequence is a graphical sequence if and only if the sequence
obtained by deleting the largest entry d
and subtracting 1 from each of the d next largest entries is graphical. (V. Havel,1955). This operation on a sequence is called Havel’s reduction.
9. A nonincreasing
sequence of nonnegative integers d1, d2, . . . , dn is graphical if and only if its sum is even, and for k = 1, 2, . . . , n,
.
(P. Erd˝os and T.
Gallai,1960)
10. In a computer, a graph
is commonly represented as a structure with variable value. The empty graph is
often used as the initial value of a graph variable, analogous to the way in
which zero is used as the initial value of a numeric variable.
Examples:
1. The following figure
gives examples of the various varieties of graphs. (See the table of Fact 2.)

2. Computer programming flowchart (always a digraph): Each vertex represents some programmed operation or
decision, and each arc represents the flow of control to the next operation or
decision.

3. Model for social networks (usually undirected): Each vertex represents a person in the network,
and each edge represents a form of interaction between the persons represented
by its endpoints. This is illustrated by the following graph.

4. Model for road networks (most edges undirected): Each vertex represents either an intersection
of two roads or the end of a dead-end street. The absence of an endpoint in the
illustration indicates that the road continues beyond what is shown. Direction
on an edge may be used to indicate a one-way road. Undirected edges are two-way
roads.

5. In the following graph
with vertex set V = { v1, v2, v3, v4, v5 } and edge set
E = { e1, e2, e3, e4, e5, e6, e7 }, the vertex v5 is an isolated point, and the degree sequence is (0,3,3,4,4). The edge e7 is a loop, and the three edges e4, e5, and e6 form a multi-edge.

6. Deleting the isolated
vertex and the self-loop in Example 5 and then reducing the multi-edge to a
single edge yields the following simple graph, whose degree sequence is (1,2,2,3).

7. The
sequence (1,2,2,3,4,5) is not graphical, by Euler’s
theorem (Fact 4), because its sum is odd.