Special Graphs

Graph Theory · Axiom Academy

A visual gallery of important graph families in Graph Theory 1. Empty Graph (Null Graph) E n or N n The empty graph (also called the null graph ) on n vertices has no edges at all - just isolated vertices with no connections between them. Every vertex has degree 0 (isolated) Complement of complete graph K n A path graph P n consists of n vertices arranged in a line, with edges connecting consecutive vertices. It is the simplest connected graph. Two vertices of degree 1 (endpoints), others degree 2 Diameter: n-1 (maximum distance between any two vertices) A tree (connected acyclic graph) A cycle graph C n forms a closed loop by connecting n vertices in a circle. It is formed by adding one edge to a path to connect its endpoints. All vertices have degree 2 (2-regular) Bipartite if and only if n is even Girth: n (length of shortest cycle) A complete graph K n has an edge between every pair of distinct vertices. It is the densest simple graph possible. (n-1)-regular (every vertex has degree n-1) Diameter: 1 (every pair of vertices is adjacent) A star graph S n consists of one central vertex connected to n outer vertices, with no edges between the outer vertices. It is also the complete bipartite graph K 1,n . Center vertex has degree n, outer vertices degree 1 Is a tree (minimizes diameter among trees) A wheel graph W n is formed by connecting a single central vertex (the hub) to all vertices of a cycle C n . The parameter n refers to the number of vertices in the outer cycle.

This is the written version of the interactive lesson above. See the full Graph Theory course.