Let’s talk a bit about graphs, being a tad more formal about them.
A graph G is a pair (V,E) where V is a non-empty set of *objects* called vertices, and E is a set of pairs of elements of V called edges where a pair x={a,b} means that
vertices a and b are *adjacent*. We also say that edge x is *incident on* both a and b.
The number of edges that are incident on a vertex is called the *degree* of a vertex.
Take any graph G, and take the sum of the degrees of all vertices. That number will
be 2×|E| (2 times the cardinality of the set of edges.) This should be pretty obvious: since each edge has two ends, each edge adds to the degree of two different vertices.
Already, we can show a moderately interesting fact. You *can’t* draw a graph with an odd number of vertices where the average degree of the vertices is three. It’s easy to prove: the number of edges in the graph is 1/2 the sum of the degrees of the vertices. So for a graph with N vertices and average degree three, the sum of the degrees of all vertices is N×3. If N is odd, then N×3 is odd. But the sum of the degrees of all vertices *must* be even. Presto – can’t happen. (Typo corrected in this paragraph; 1/2 was written 1/3.)
Ok, it’s trivial, but it’s cute. Moving on…
What does equality mean in terms of graphs? We say two graphs are equivalent or *isomorphic* if and only if there is a one-to-one mapping between the vertices which preserves the adjacencies created by the edges. The shape of the graph doesn’t matter – just how the vertices are connected to one another. Another way of stating isomorphic equivalence is that two graphs are isomorphic if and only if you can re-arrange the vertices of one without breaking any edges so that the two graphs are identical. So the two graphs to the right are isomorphic: one possible isomorphic map is (a→e), (b→f), (c→g), (d→h).
On the other hand, you might think that the two graphs next to this paragraph are isomorphic – but you’d be wrong. There’s no way no rearrange the vertices to make these equivalent. It looks like as long as you map d to w and a to u that they’re isomorphic. But look more closely – a is adjacent to three vertices with degree 3 (b,c,e) and one with degree 4 (f); u is adjacent to 2 vertices with degree 3 (v,z) and two with degree 4 (w,y). There are no vertices in the left-hand graph adjacent to two vertices with degree 4.
And now, just to get them out of the way, here’s a bunch of definitions:
* Given two graphs, A=(V,E) and B=(W,F), B is a *subgraph* of A if and only if (W⊆V), and F⊆E. (You might think that we’d need to have an extra condition to say that the edges in F only include vertices in W; we don’t need to, because we said that (W,F) was a graph, which means that F only includes the vertices in W.)
* If you can re-arrange a graph so that all if its edges can be draw without any of the edges crossing, then it’s called a *planar* graph. For example, if you look at first example to the right, you can see that the graph is planar – even though it is drawn with its edges crossing, it can be rearranged into the shape of the other, where no edges cross.
* If every vertex of a graph is adjacent to every other vertex, then the graph is called a clique. The graph to the right is a 5-clique – the clique with 5 vertices.
* If there is at least one path from any node to any other node, then the graph is *connected*.
* If there’s a path from any node in the graph back to itself, then the graph is cyclic.