Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 36 · Getting Started

Kinds of Graphs

Tour the main kinds of graphs: simple, directed, weighted, multigraphs, complete, bipartite, paths, cycles and trees, with Python checks for each property.

So far every edge has been a plain two-way line. Real problems need more: one-way streets, road lengths, two flights on the same route. Graph theory therefore has a family of graph types. This lesson is a guided tour. You will meet each one again in later chapters.

Simple graphs, loops and multigraphs

A simple graph has no loops (an edge from a vertex to itself) and no parallel edges (two edges between the same pair). Unless stated otherwise, "graph" in this tutorial means a simple graph.

A multigraph allows parallel edges. Two different bus lines between the same pair of stops are parallel edges. A pseudograph allows loops as well. A loop adds 2 to the degree of its vertex, so the handshake lemma from graph terminology still holds.

graph LR
  A -- "bus 1" --- B
  A -- "bus 2" --- B
  B --- C

Two parallel edges between A and B make this a multigraph.

Directed graphs

In a directed graph (digraph) each edge has a direction: it goes from a tail to a head, written (u, v). Think of one-way streets, "follows" on a social network, or hyperlinks.

Degrees split in two: the in-degree is the number of edges coming in, the out-degree the number going out. The sum of all in-degrees equals the sum of all out-degrees, and both equal m.

graph LR
  a --> b
  b --> c
  c --> a
  c --> d

Here a, b, c form a directed cycle and d is a dead end: out-degree 0.

Python In-degree and out-degree

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Weighted graphs

A weighted graph attaches a number, the weight, to every edge: a distance, a cost, a capacity or a probability. Algorithms such as Dijkstra and minimum spanning trees need weights. Weights may be negative in some applications (for example profit and loss), which changes which algorithms are correct.

Named families

Some graphs are common enough to have names:

Name Notation Description
Complete graph K_n Every pair of vertices is adjacent
Path P_n Vertices in a line: n vertices, n-1 edges
Cycle C_n A path whose ends are joined: n vertices, n edges
Star K_{1,n} One center joined to n leaves
Wheel W_n A cycle plus a hub joined to every cycle vertex
Complete bipartite K_{a,b} Two groups; every vertex of one joined to every vertex of the other
Hypercube Q_d Vertices are d-bit strings; edges join strings that differ in one bit

Bipartite graphs

A graph is bipartite if its vertices can be split into two groups so that every edge goes between the groups, never inside one. Matching students to projects, workers to jobs or users to products gives bipartite graphs. A neat characterization is that a graph is bipartite exactly when it has no odd cycle. We return to this in the coloring chapter of the track (Graph Theory).

You can test it by trying to color vertices with two colors so that each edge joins different colors:

Python Two-coloring test for bipartite graphs

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Subgraph-like vocabulary

A connected graph lets you get from any vertex to any other along edges; we study this in walks, paths and cycles. A tree is a connected graph with no cycles (trees and forests). A DAG (directed acyclic graph) is a digraph with no directed cycle, and it is the natural model for "task A must come before task B".

Counting edges in the families

Use the handshake lemma to check your formulas:

Python Edge counts of named graphs

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which type of graph allows two edges between the same pair of vertices?

    Parallel edges are allowed in multigraphs and excluded from simple graphs.
  2. 2. In a directed graph with 7 edges, what is the sum of all out-degrees?

    Each edge leaves exactly one vertex, so the out-degrees sum to the number of edges, 7. The same is true for in-degrees.
  3. 3. How many edges does the cycle C_9 have?

    A cycle on n vertices has n edges, so C_9 has 9.
  4. 4. A graph is bipartite exactly when it has:

    Bipartite graphs may contain cycles, but only even ones. Any odd cycle makes two-coloring impossible.

Summary

  • Simple graphs have no loops or parallel edges; multigraphs allow parallel edges, pseudographs loops too.
  • Directed graphs have in-degree and out-degree; both sums equal m.
  • Weighted graphs attach a number to each edge.
  • Named families: K_n, paths, cycles, stars, wheels, complete bipartite graphs and hypercubes.
  • A bipartite graph can be two-colored and has no odd cycle.

Next: The Seven Bridges of Königsberg