Graphs

A graph and its constituent parts

Imagine some dots. Let’s give these dots a name—vertices. Now imagine some lines, each connecting one dot to another. Let’s call these edges. This structure we just built in our mind is an example of what we want to conceive as a graph.

Of course, we want a more precise definition, so we know exactly what constitutes a graph and what doesn’t.

A graph $G$ consists of a non-empty set $V$, whose elements are called vertices, and a set $E$, whose elements are called edges, such that each edge is associated with one or two vertices called its end-vertices.

We use the notation $G = (V, E)$ to highlight that $V$ is the vertex set and $E$ ...