Using your Head is Permitted

March 2016 riddle

This month's puzzle is a follow-up question for the December 2015 riddle and comes from Radu-Alexandru Todor. (Thanks, Radu!)

Spoiler alert: The following description contains hints regarding the solution of the December 2015 riddle. If you still mean to tackle that other riddle, you may want to hold on before you continue to this one.

Radu asks: What is the maximal ratio that can be attained between the number of appearances of C4 in a graph G and the number of appearances of the most common induced connected subgraph of G, for any non-empty G? (In this context, "most common" need not be unique.)

I add to this: Describe, explicitly, a G that attains this ratio.

As usual, all answers must come with a proof. See the December 2015 riddle for definitions of the terminology used here.

List of solvers:

Dan Dima (8 March 01:10)

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