Basic Notation and Terminology for Graphs

A graph \(\bfG\) is a pair \((V,E)\) where \(V\) is a set (almost always finite) and \(E\) is a set of \(2\)-element subsets of \(V\). Elements of \(V\) are called vertices and elements of \(E\) are called edges. We call \(V\) the vertex set of \(\bfG\) and \(E\) is the edge set. For convenience, it is customary to abbreviate the edge \(\{x,y\}\) as just \(xy\). Remember though that \(xy\in E\) means exactly the same as \(yx\in E\). If \(x\) and \(y\) are distinct vertices from \(V\), \(x\) and \(y\) are adjacent when \(xy\in E\); otherwise, we say they are non-adjacent. We say the edge \(xy\) is incident to the vertices \(x\) and \(y\).

For example, we could define a graph \(\GVE\) with vertex set \(V=\{a,b,c,d,e\}\) and edge set \(E=\{\{a,b\},\{c,d\},\{a,d\}\}\). Notice that no edge is incident to \(e\), which is perfectly permissible based on our definition. It is quite common to identify a graph with a visualization in which we draw a point for each vertex and a line connecting two vertices if they are adjacent. The graph \(\bfG\) we've just defined is shown in . It's important to remember that while a drawing of a graph is a helpful tool, it is not the same as the graph. We could draw \(\bfG\) in any of several different ways without changing what it is as a graph.

As is often the case in science and mathematics, different authors use slightly different notation and terminology for graphs. As an example, some use nodes and arcs rather than vertices and edges. Others refer to vertices as points and in this case, they often refer to lines rather than edges. We will try to stick to vertices and edges but confess that we may occasionally lapse into referring to vertices as points. Also, following the patterns of many others, we will also say that adjacent vertices are neighbors. And we will use the more or less standard terminology that the neighborhood of a vertex \(x\) is the set of vertices adjacent to \(x\). Thus, using the graph \(\bfG\) we have depicted in , vertices \(d\) and \(a\) are neighbors, and the neighborhood of \(d\) is \(\{a,c\}\) while the neighborhood of \(e\) is the empty set. Also, the degree of a vertex \(v\) in a graph \(\bfG\), denoted \(\deg_\bfG(v)\), is then the number of vertices in its neighborhood, or equivalently, the number of edges incident to it. For example, we have \(\deg_\bfG(d)=\deg_\bfG(a)=2\), \(\deg_\bfG(c)=\deg_\bfG(b)=1\), and \(\deg_\bfG(e)=0\). If the graph being discussed is clear from context, it is not uncommon to omit the subscript and simply write \(\deg(v)\) \(\deg_\bfG(v)\) degree of vertex \(v\) in graph \(\bfG\) for the degree of \(v\).

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.