Graphs, Vertices and Edges, Part I

Throughout this series we'll take a double sided approach. On one side I'll give the technical, mathematical definition. On the other side, will be an informal, English definition of the same concept. If we're going to talk about graph theory it makes sense that we should start with the definition of a graph.

What You Should Learn

  • The technical definition of a graph and how it relates to a physical picture.
  • The names of the parts of a graph.
circuit board

The points and connections on a circuit board are a real world example of a graph.

A graph G is a finite, nonempty set V and in irreflexive, symmetric relation R on V. We will use E to denote the set of symmetric pairs in R. Each element of V is called a vertex. Each element of E is called an edge.

I find that it's easiest to think of graphs visually. Think of the elements of V as points and the elements of E as segments connecting the points. If you think of it this way the names, vertices and edges, dovetail perfectly with the way they're used in geometry to refer to the points and sides of polygons.

Let's take a concrete example and look at it from both perspectives.

Let V = { v1, v2, v3, v4, v5 } and let R = { (v2, v3), (v3, v2), (v1, v3), (v3, v1), (v2, v5), (v5, v2), (v5, v3), (v3, v5), (v4, v5), (v4, v5) }.

Notice that the elements of V come in pairs. In other words, if (v3, v1) is in R then (v1, v3) must be in it also. This is what's required by the "symmetric" part of the definition. (Later on we'll take away this requirement to get what's called a directed graph.) These symmetric pairs are what make up the elements of E or the edges of the graph.

The picture below illustrates the graph. First, notice that it has all the same vertices as the technical example: v1, v2, v3, v4 and v5. To draw the lines I looked at every pair of points in R and draw a segment connecting them.

graph 1

How did I decide where to put the points? The only thing we care about is how the points are connected, not where they are in relation to each other so, ultimately, it doesn't matter. In this specific case, I arranged them so that the segments didn't overlap just to make the diagram easier to read.

Graphs, Vertices and Edges, Part II >>