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$ is the edge set of a graph $G$.

A vertex can also be referred to as a node. An edge with only one end-vertex is called a loop or a self-loop.

Simple graphs

Some applications of graphs allow multiple edges between the same pair of vertices, while others allow loops. A graph without loops and with at most one edge appearing between any pair of vertices is called a simple graph. Graphs that are not simple are called non-simple graphs.

Convention: When the qualifier “simple” or “non-simple” is omitted, it is assumed that the graph is simple.

Notations for vertices and edges

• We denote a vertex by a letter in lowercase, such as $u$, $v$, or $w$. With many vertices, we prefer naming them by numbering them using subscripts $v_1, v_2, \ldots, v_n$.

• Likewise, we can denote an edge by a lowercase symbol like $e$ or $e_1, e_2, \ldots , e_m$.

  However, for simple graphs, we typically denote an edge by putting together, in any order, the names of its end-vertices. For instance, $(u,v)$ denotes an edge with end-vertices $u$ and $v$. Clearly, $(u,v)$ and $(v,u)$ denote the same edge.

Adjacency, incidence, and degree

In the example below, see how vertices $u$ and $v$ are neighbors—in the sense that an edge joins them directly. Such pairs of vertices are said to be adjacent to each other.

Adjacent vertices are vertices having an edge joining them.

One more note on usage:

An edge is said to be incident on a vertex if that vertex is its end-vertex.

So, for example, the edge $(u,v)$ is incident on the vertex $u$. It is also incident on the vertex $v$.

The degree of a vertex is the number of edges incident on that vertex, except that each loop is counted twice.

The reason we count a loop twice is that we want the degree of a vertex to signify the number of ends of edges sticking out of that vertex.

Select a vertex in the following example to see its degree:

Graphs are not geometric figures

All the pictures we saw above may have created the illusion that the edges are line segments and are at specific angles to each other. However, that’s not true at all! Think back to the definition. The graph drawing is just a representation of the graph structure.

In fact, given a graph drawing, we can redraw the same graph by moving its vertices and edges around and changing the curvature of the edges.

Try dragging vertices to see different ways to draw the same graph: