Random Graph Examples

Distance and Diameter Example

Given the following graph:

Distance in a graph - example - graph

We would have the following table:

Distance in a graph - example - table

The value for $d(x, 2) * d(1, y) = 1$ means that when the starting vertex is $1$ and the ending vertex is $2$, then the distance is $1$.

You could read that the diameter is $4$ because the longest path is $7-6-4-5-2$ (4 edges) (or $2-5-4-6-7$).

Matching In A Graph Example

Give a maximal matching, maximum matching, and perfect matching of the Petersen graph $G$.

Example - Graph G

Legend

  • Red 🔴: we picked this edge
  • Blue 🔵: we removed this edge

Maximal matching:

Example - Maximal matching

Perfect/Maximum/Maximal matching:

Example - Perfect matching