What is a Graph? · Graphs

Lesson 13

Nikolai Chukhin · Alexander S. Kulikov

Informally, a graph is a collection of objects and pairwise connections between some pairs of these objects. One way to represent a graph is to draw objects as circles (or other shapes) and connect some pairs of them by segments (or curves). We've seen such pictures in the previous section.

Formally, a graph is a pair \((V,E)\) where \(V\) is a (finite) set of nodes (also known as vertices) whereas \(E \subseteq V \times V\) is a set of edges.

To give an example, let \[V=\{A, B, C, K\} \text{ and }E=\{\{A, C\}, \{B, C\}, \{B, K\}, \{K, A\}, \{K, C\}\}\ .\] The graph \((V,E)\) has four nodes and five edges. \(A\), \(B\), \(C\), and \(K\) are the name of the nodes. There are many ways to draw this graph:

One can also name individual edges in the graph. For example, we may denote the edge \(\{B,C\}\) by \(e\). We say that \(B\) and \(C\) are end-points of \(e\). We also say that \(B\) and \(e\) are incident whereas \(B\) and \(C\) are adjacent or neighbors.