This problem is about embeddings of directed graphs. A directed graph (or digraph for short) consists of a set of points called vertices and a set of edges, where each edge is directed from one vertex to another vertex.
A tree is a connected graph which contains no cycles, and an oriented tree is a digraph formed by giving a direction to each edge of a tree. The digraph T shown on the mug is an example of an oriented tree. Since this problem is about directed graphs, for the rest of this page we simply say tree to mean oriented tree.
A complete graph is a graph in which there is an edge between every pair of vertices, and a tournament is a digraph formed by giving a direction to each edge of a complete graph. The digraphs G1, G2, and G3 shown on the mug are examples of tournaments.
Whether you can find a copy of a given digraph within another given digraph is a fundamental question of graph theory, and the mug depicts one instance of this problem: can you find a copy of T in G for G = G2 and G = G3? This means that you must map each vertex x of T to a vertex f(x) of G so that
- different vertices of T map to different vertices of G, i.e. if x ≠ y then f(x) ≠ f(y), and
- the directions of edges are respected, meaning that if there is an edge in T directed from x to y then there must be an edge in G directed from f(x) to f(y).
The bold edges in the tournament G1 show where you can find a copy of T in G1; the image below makes clear which vertex maps to which in this copy.