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 C_{3} as its most common induced
subgraph or prove that none such exists.
## Part 2:Repeat, with C_{4} instead of C_{3}.
Some explanations regarding the terminology: - A "graph" is a set of vertices and a set of edges connecting pairs of vertices.
- 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. - 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*. - C
_{3}is the cycle of length three, i.e. the triangle. (See image (a) below.) C_{4}is the cycle of length four, i.e. the square. (See image (b) below.)
In the graph of image (c), as an example, C |
## 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 __riddlesbrand.scso.com__.
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.

Enjoy!