Vertices and Edges Explained

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. The formal definition of a graph

Almost every introduction says a graph is "dots joined by lines". That picture is useful and it is also the reason so many people get stuck later: the dots and the lines are not the mathematical object. The object is a pair of sets.

Diestel's Graph Theory, the standard graduate reference, opens with the definition in its cleanest form:

A graph is a pair G = (V, E) of sets such that E ⊆ [V]², where [V]² denotes the set of all 2-element subsets of V.

Unpack that and everything else in this article follows:

• V is a set of objects called vertices. Nothing is assumed about them. They can be cities, people, web pages, chemical atoms or integers. The theory never looks inside them; it only cares which ones are distinguishable.
• E is a set of 2-element subsets of V. An edge is literally the set {u, v}, not an arrow or a curve. It records nothing except which pair it joins.
• Because E is a set, an edge is either present or absent. It cannot appear twice.
• Because each element of E has exactly two distinct members, an edge cannot join a vertex to itself.

Those last two consequences are not restrictions someone added later. They fall straight out of the set theory, and a graph that obeys them is called simple. Allowing repeated edges or self-loops means changing the definition itself, which is section 4.

Two more pieces of standard notation you will meet everywhere. When several graphs are in play, write V(G) and E(G) to say which graph you mean. And the two size measures have names: the number of vertices is the order of the graph, the number of edges is its size. Most algorithm texts abbreviate these to n = |V| and m = |E|, and that is the convention used throughout this site.

This graph is the running example for the rest of the article. Its vertex set is V = {A, B, C, D, E, F}, so the order is n = 6, and its edge set is

E = { {A,B}, {A,C}, {B,C}, {B,D}, {C,D}, {D,E}, {E,F} }        so  m = 7

2. Vertices: what they are, and what they are not

A vertex carries no structure of its own. In the formal object it is an anonymous element of a set, and everything you can say about it comes from the edges that touch it. This is worth insisting on, because it is exactly what makes graph theory transferable: a theorem proved about vertices is a theorem about airports, transistors, proteins and Git commits at the same time.

Three consequences that trip people up in practice:

• Vertices are distinguishable but otherwise interchangeable. Two graphs that differ only in what the vertices are called are isomorphic, and graph theory treats them as the same graph. When you label vertices in code you are adding bookkeeping, not mathematics.
• An isolated vertex is still a vertex. A vertex with no edges at all is perfectly legal and is called isolated. Beginners often build a graph from an edge list and silently lose every isolated vertex, which changes the order of the graph and quietly breaks anything that divides by n.
• The empty graph exists, and so do infinite ones. Nothing in the definition forbids V = ∅, and nothing in it forbids V being infinite either, which is the subject of the guide on finite and infinite graphs. Most texts allow it and a few exclude it by fiat; the important thing is to know which convention your source uses before you trust an edge case.

The historical note is worth a line, because the vocabulary is not stable across a century of literature. Harary's classic 1969 text calls them points and lines. Physicists and many applied papers say nodes and links. Chemists, following Sylvester's 1878 note in Nature that gave the subject the word "graph" in the first place, spoke of atoms and bonds. All four vocabularies describe the same pair of sets.

3. Edges, adjacency and incidence

An edge joins exactly two vertices, and those two are its endpoints or ends. From that single relationship the two words that beginners most often swap get their precise meanings:

• Adjacency is a relation between two vertices. Vertices u and v are adjacent, written u ~ v, when {u, v} ∈ E. Adjacent vertices are also called neighbours, and the set of all neighbours of v is its neighbourhood, written N(v).
• Incidence is a relation between a vertex and an edge. The edge {u, v} is incident to u and incident to v, and to no other vertex.

The distinction sounds pedantic until you meet a sentence like "two adjacent edges". It is legal, and it means two edges that share an endpoint. Vertices are adjacent through an edge; edges are adjacent through a vertex. Keeping the two relations apart is what lets you read a definition such as a proper colouring ("adjacent vertices get different colours") without ambiguity.

In the running example, N(B) = {A, C, D}, so B has three neighbours. The edge {B, D} is incident to B and to D. The edges {B, D} and {C, D} are adjacent to each other, since both are incident to D.

4. Loops and parallel edges: where the definition has to change

Real systems produce two things the set definition cannot express. A road that leaves a roundabout and returns to it is an edge from a vertex to itself. Two separate flights between the same pair of airports are two distinct edges joining the same pair. Under E ⊆ [V]2 neither exists: {A, A} is a one-element set, and a set cannot hold the same element twice.

The fix is not a footnote, it is a different definition. Bondy and Murty's Graph Theory carries an explicit incidence function alongside the two sets:

G = (V, E, ψ)      where  ψ: E → unordered pairs of (not necessarily distinct) vertices

Now an edge is an object in its own right with an identity, and ψ reports which pair it joins. Two different edges may map to the same pair, which gives parallel edges, also called multi-edges. An edge may map to a pair whose two entries coincide, which gives a loop. West's Introduction to Graph Theory takes the same route, defining a graph as a vertex set, an edge set, and a relation associating each edge with its endpoints.

The resulting vocabulary:

Two practical warnings. First, "multigraph" is not used consistently: some authors let it include loops, others do not, so check the source before quoting a theorem. Second, a loop contributes 2 to the degree of its vertex, not 1, because both of its ends attach there. That convention is not arbitrary, and the next section explains exactly why it has to be that way.

Unless a text says otherwise, "graph" means "simple graph". Every result in the rest of this article assumes it, and the companion guide on simple graphs vs multigraphs works through exactly what the two allowances change and which standard bounds stop holding without them.

5. Degree and the first theorem in graph theory

The degree of a vertex v, written deg(v) or d(v), is the number of edges incident to it. Equivalently, and more usefully, it is the number of edge ends that meet at v. In a simple graph it equals the size of the neighbourhood, deg(v) = |N(v)|.

Two related quantities appear constantly in bounds and proofs: the minimum degree δ(G) and the maximum degree Δ(G). A graph in which every vertex has the same degree k is k-regular.

Now the oldest theorem in the subject, which comes from Euler's 1736 paper on the bridges of Königsberg, the paper that founded graph theory:

Handshaking lemma. For every finite graph, the sum of all vertex degrees equals twice the number of edges: ∑v∈V deg(v) = 2m.

The proof is one line of double counting. Count the pairs (vertex, edge end meeting it). Summing over vertices gives ∑ deg(v). Summing over edges gives 2m, since every edge has exactly two ends. Both count the same finite set, so they are equal. Notice that this argument is also what forces a loop to count twice: a loop still has two ends, and both land on the same vertex.

Check it on the running example: the degrees are 2, 3, 3, 3, 2, 1, which sum to 14, and the graph has 7 edges. The lemma has an immediate and very useful corollary.

Corollary. In any graph, the number of vertices of odd degree is even.

Split the sum into odd-degree and even-degree vertices. The total is even and the even-degree part is even, so the odd-degree part must be even too, which forces the count of odd terms to be even. That is why a party can never contain exactly three people who have each shaken an odd number of hands, and it is the same parity argument that decides whether an Eulerian path exists.

6. Degree sequences: which lists of numbers are graphs

Write the degrees in non-increasing order and you get the degree sequence. For the running example it is (3, 3, 3, 2, 2, 1). The natural question runs the other way: given a list of numbers, is there a graph with exactly those degrees? A list for which one exists is called graphic.

The handshaking lemma already rules out half the candidates: any sequence with an odd sum is not graphic. But that test is far from sufficient. Consider (3, 3, 1, 1). The sum is 8, which is even, and no vertex asks for more than the 3 neighbours available. Yet no simple graph realises it: the two degree-3 vertices must each join all three other vertices, which forces both degree-1 vertices to have degree 2.

Two classical results settle the question completely:

• The Erdős–Gallai theorem (1960) gives an exact criterion: a non-increasing sequence with even sum is graphic if and only if, for every k, the sum of the first k terms is at most k(k-1) plus the sum over the remaining terms of min(di, k). It is a closed-form test, checkable in linear time after sorting.
• The Havel–Hakimi algorithm, from Havel (1955) and independently Hakimi (1962), is the constructive version: remove the largest degree d, subtract 1 from the next d entries, re-sort, and repeat. The original sequence is graphic exactly when this reduction ends in all zeros, and the steps double as a recipe for building a graph that realises it.

Run Havel–Hakimi on the failing example to see it work:

(3, 3, 1, 1)   remove the 3, subtract 1 from the next three entries
(2, 0, 0)      re-sorted
               remove the 2, subtract 1 from the next two entries
(-1, -1)       negative, so the sequence is NOT graphic

And on the running example, where it succeeds:

(3, 3, 3, 2, 2, 1)  →  (2, 2, 1, 2, 1)  → sorted (2, 2, 2, 1, 1)
(2, 2, 2, 1, 1)     →  (1, 1, 1, 1)     → sorted (1, 1, 1, 1)
(1, 1, 1, 1)        →  (0, 1, 1)        → sorted (1, 1, 0)
(1, 1, 0)           →  (0, 0)           → all zeros, so the sequence IS graphic

One warning that catches people out: a graphic sequence can be realised by several non-isomorphic graphs. Knowing every degree does not pin down the graph.

7. Directed edges: arcs, in-degree and out-degree

Replace the unordered pair with an ordered pair and you get a directed graph, or digraph:

D = (V, A)      with  A ⊆ V × V

An element (u, v) of A is an arc or directed edge, running from its tail u to its head v. Because the pair is ordered, (u, v) and (v, u) are different arcs and both may be present. Bang-Jensen and Gutin's Digraphs is the standard reference for the terminology, and it keeps "arc" for the directed object precisely to avoid the ambiguity of calling both things edges.

Degree splits in two:

• Out-degree d+(v), the number of arcs with tail v.
• In-degree d-(v), the number of arcs with head v.

The handshaking lemma splits with it. Every arc has exactly one tail and exactly one head, so counting arc tails and arc heads separately gives

∑v∈V d+(v)  =  ∑v∈V d-(v)  =  |A|

Note the missing factor of 2: in the undirected case each edge contributed two ends to one sum, here each arc contributes one end to each of two sums. The full comparison, including orientations, the three kinds of connectivity and which algorithms survive, is in the guide to directed vs undirected graphs. Vertices with in-degree 0 are sources and those with out-degree 0 are sinks, which is exactly the vocabulary topological sorting and network flow are built on.

8. Weighted edges, and why weights sit outside the graph

Shortest path problems need distances, flow problems need capacities, and scheduling problems need durations. None of that is in G = (V, E), and it is not supposed to be. A weighted graph is a graph plus a function:

w: E → ℝ        assigning a real number to each edge

Keeping the weights in a separate function rather than inside the edges is what lets one graph carry several cost models at once. The same road network is one graph with three weight functions: kilometres, minutes and fuel. The companion guide on weighted vs unweighted graphs follows that idea through algorithm choice, negative weights and vertex strength. Swapping the function changes every shortest path without touching a single vertex or edge.

It also explains why algorithms come with conditions on w rather than on the graph. Dijkstra's algorithm requires w(e) ≥ 0 for every edge; Bellman-Ford tolerates negative weights but not negative cycles. Those are constraints on the function, and the underlying pair of sets is indifferent to them.

9. How many edges can a graph have?

In a simple graph on n vertices, an edge is a choice of 2 distinct vertices from n, so the maximum is the binomial coefficient

mmax = C(n, 2) = n(n - 1) / 2

The graph that achieves it, where every pair of vertices is adjacent, is the complete graph Kn. For the running example, n = 6 gives a ceiling of 15 edges, and the graph uses 7 of them. The ratio 2m / (n(n-1)) is the density, here 0.47.

That single bound is the reason two phrases dominate the algorithms literature:

• A dense graph has m close to its maximum, so m = Θ(n2).
• A sparse graph has m far below it, typically m = O(n) or O(n log n). Almost every large real network is sparse: road maps, social graphs and web graphs all have average degree in the single or double digits regardless of how many vertices they hold.

Sparsity is not a detail. It decides which data structure to use, which is the next section, and it is why a complexity of O(m log n) beats O(n2) on real inputs even though the two are identical in the worst case.

10. Storing vertices and edges in code

There are three standard ways to hold V and E in memory, and the trade-offs between them are set out in Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms. The full comparison, including compressed sparse row and the density threshold at which a matrix becomes the smaller option, is in the guide to graph representation.

The practical rule follows from section 9. Traversals such as BFS and DFS spend their whole running time walking neighbour sets, so on a sparse graph the adjacency list gives O(n + m) where the matrix would force O(n2) just to scan rows of zeros. On a dense graph the matrix wins on both space and simplicity. An edge list looks primitive until you meet Kruskal's algorithm, which sorts all edges by weight and never needs neighbour lookups at all.

11. Deciding what a vertex should be

The hardest part of applying graph theory is not any theorem. It is choosing what the vertices are, because that choice fixes everything downstream and is rarely unique.

Take a road network. The obvious model makes intersections the vertices and road segments the edges, which is what a routing engine wants: a path in the graph is a route on the ground. But turn restrictions and turn costs live at intersections, not on roads, and this model has nowhere to put them. The standard fix inverts the choice: make each road segment a vertex, and join two of them when you may legally drive from one into the other. Now a turn is an edge and can carry a cost.

That inversion is a formal construction, not a hack. The line graph L(G) has one vertex for every edge of G, with two of them adjacent when the corresponding edges of G share an endpoint. It goes back to Whitney's 1932 paper on congruent graphs, and it is the reason a problem about edges can often be handed to an algorithm that only knows about vertices. Matching problems, for instance, become independent-set problems on the line graph.

A short checklist that catches most modelling mistakes:

• Can two of your vertices be joined more than once? If yes you need a multigraph, or you need to aggregate the parallel edges into one weight.
• Is the relation symmetric? "Is friends with" usually is, "follows" and "depends on" are not. Get this wrong and you will use an undirected algorithm on a directed problem.
• Does the relation involve more than two things at once? An edge joins exactly two vertices. A committee of five people, or a chemical reaction with three reagents, is a hypergraph edge, and squashing it into ordinary edges loses information.
• Does the structure change over time? A standard graph is a snapshot. Temporal or dynamic graphs are separate models with their own literature.

12. Terminology traps across textbooks

Graph theory grew in several fields at once, so the same object has several names and a few names mean different things to different authors. These are the ones that actually cause errors:

The safe habit is the one every paper follows: state your conventions once at the start, then hold to them. When you quote a theorem, quote the definition it was proved under.

13. Glossary of symbols

The notation used across this site and in the references below.

15. References

The definitions, theorems and attributions above come from these sources, listed in chronological order.

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (published 1741), 128 to 140. The Königsberg bridges paper, and the origin of the degree argument.
2. Sylvester, J. J. (1878). "Chemistry and Algebra." Nature 17, 284. The note that introduced the word "graph" in its modern sense.
3. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1), 150 to 168. Source of the line graph construction.
4. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft. The first book devoted entirely to graph theory.
5. Havel, V. (1955). "A remark on the existence of finite graphs" (in Czech). Časopis pro pěstování matematiky 80, 477 to 480.
6. Erdős, P. and Gallai, T. (1960). "Graphs with prescribed degrees of vertices" (in Hungarian). Matematikai Lapok 11, 264 to 274. The exact criterion for graphic sequences.
7. Hakimi, S. L. (1962). "On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I." Journal of the Society for Industrial and Applied Mathematics 10(3), 496 to 506.
8. Harary, F. (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley. The classic that calls vertices "points" and edges "lines".
9. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. New York: Springer.
10. West, D. B. (2001). Introduction to Graph Theory, 2nd edition. Upper Saddle River: Prentice Hall. Defines a graph by a vertex set, an edge set and an endpoint relation.
11. Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer. Source of the incidence function formulation used in section 4.
12. Bang-Jensen, J. and Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2nd edition. London: Springer. Standard reference for arcs and directed degrees.
13. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms, 3rd edition. Cambridge, Massachusetts: MIT Press. Source of the representation costs in section 10.
14. Diestel, R. (2017). Graph Theory, 5th edition. Graduate Texts in Mathematics 173. Berlin: Springer. Source of the definition quoted in section 1.