Graphs, Degree and Trees

Vertices, Edges and Degree #

The degrees always total twice the edges.

A graph is vertices joined by edges, and a degree counts the edge ends at one vertex

A graph is a set of vertices, drawn as dots, joined by edges, drawn as lines.

The degree of a vertex counts the edges meeting it, so B has degree 3.

Every vertex carries its own degree: 2, 3, 3, 3 and 1.

Those degrees total 12, and this graph has 6 edges. Twelve is twice six.

One edge adds 1 at each of its two ends, so the degrees always total twice the edges.

Simple, Complete and Bipartite Graphs #

Graphs named by the pattern of their edges.

A simple graph has no loop and no repeated edge, and a complete graph joins every pair

A joins itself with a loop, and two separate edges both join B to C.

Take both away and the graph is simple: no loop, and at most one edge per pair.

A complete graph joins every pair. Four vertices give 6 edges, and every degree is 3.

Each of n vertices meets n − 1 others, and each edge is counted twice: $\frac{n\left(n-1\right)}{2}$n(n − 1)/2.

A bipartite graph splits the vertices into two sets, and every edge crosses between them.

Subgraphs, Connectedness and Trees #

Connected, no cycle, one edge fewer than vertices.

A tree is a connected graph with no cycle, so it has one fewer edge than it has vertices

A graph is connected when a route joins every pair of vertices. This one is not.

One more edge joins the two pieces, and now every vertex can reach every other.

A subgraph keeps some of the vertices and some of the edges, and nothing else.

This subgraph is a tree: connected, and exactly one route between any two vertices.

There are six vertices and five edges. A tree always has one fewer edge than vertices.

The dashed edge would close the cycle A-B-C, so the result would not be a tree.

Directed Graphs and Strong Connectedness #

Arrows in, arrows out, and where they let you go.

A directed edge points one way, giving each vertex an in-degree and an out-degree

A directed graph gives every edge a direction, drawn as an arrow.

Arrows arriving give the in-degree and arrows leaving give the out-degree.

Every arrow leaves one vertex and arrives at another, so both totals come to 5.

Following the arrows, A to B to D to C and back to A reaches every vertex: the graph is strongly connected.

Turn one arrow around and nothing reaches A, so the graph is no longer strongly connected.