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:
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 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.
Back to main page