Graphs: Vertices, Edges and Their Properties

A graph is a set of things, called vertices, and a set of connections between pairs of them, called edges. This card covers the words used to describe a graph, the three properties that decide how one is stored and searched, and V and E, the two sizes every graph cost is stated in. Friendships, road junctions, web pages and links, tasks and the tasks they wait for: each is a graph, and the same handful of representations stores all of them.

Two vertices joined by an edge are neighbours, and the number of edges at a vertex is its degree. V is the number of vertices and E the number of edges.

The graph below has five vertices, A to E, and six edges. It is the example for the whole topic.

Here V is 5 and E is 6. B and C each have degree 3, and A, D and E each have degree 2. A run that built the graph added the five degrees and got 12, twice E, because every edge has two ends and adds one to the degree of each.

A map of towns and roads is the usual picture, and it holds for vertices, edges and degree. It breaks at position. A road map puts each town where it is, while a graph holds only the connections: drawing A at the bottom of the page changes nothing, and two diagrams that look nothing alike can show the same graph.

Three properties decide most of what follows, and the table gives each one with the question it answers.

The example graph is undirected, unweighted and cyclic: a run found the cycle A, B, C, A. A directed graph with no cycles has its own name, a directed acyclic graph, and it describes anything that must happen in an order, such as build steps or course prerequisites. A tree is a special case of a graph: connected, with no cycles, and with exactly one path between any two vertices.

Every graph cost is written in V and E, because a graph can have many vertices and few edges, or few vertices and nearly every pair joined. An undirected graph has at most V × (V - 1) / 2 edges, which is 10 for these five vertices.