Using your Head is Permitted

December 2015 riddle

UPDATE (3 December): We are only interested in subgraphs that are connected. I have updated bullet number 3 to clarify this point.

This month's question comes from Srinibas Swain. (Thanks, Srinibas!) It has two parts. Answer both for credit.

Part 1:

Find (with proof) a graph that has C3 as its most common induced subgraph or prove that none such exists.

Part 2:

Repeat, with C4 instead of C3.

Some explanations regarding the terminology:

  1. A "graph" is a set of vertices and a set of edges connecting pairs of vertices.
  2. An "induced subgraph" of a graph G is the graph created by picking a subset of the vertices and all edges connecting them. The order in which vertices are picked is immaterial.
  3. The number of appearances of a graph, G, as an induced subgraph of another graph, H, is the number of distinct induced subgraphs of H that are isomorphic to G (i.e., have the same shape). For G to be the most common induced subgraph of H requires for the number of appearances of G as an induced subgraph of H to be strictly larger than the number of appearances of any other connected G' as an induced subgraph of H.
  4. C3 is the cycle of length three, i.e. the triangle. (See image (a) below.) C4 is the cycle of length four, i.e. the square. (See image (b) below.)

In the graph of image (c), as an example, C3 appears twice as an induced subgraph, but C4 does not appear at all. (It appears as a subgraph, but not as an induced subgraph, because an induced subgraph includes all edges connecting the subset of vertices chosen.) The most common induced subgraph of the graph of image (c) is the single edge. It appears 5 times.

List of solvers:

Lorenz Reichel (4 December 08:04)
Radu-Alexandru Todor (23 December 12:43)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page