In the excellent paper On the power of two, three, and four probes It is well known that every graph with s vertices and at least 2s edges contains a cycle of

It is well known that every graph with s vertices and at least
2s edges contains a cycle of length at most 2log s

My students puzzled over this one in two ways.
(1) How to prove it? Two of them came up
with correct proofs that were not that hard.
(2) Is it really well known? Two of them searched the web for a proof.
They could not find one.

The problem with the phrase It is well known that
is that it may be well known to people who know it (duh) but
not to others. People not in the know don't even know if
its hard or not (its not).
Perhaps they should have said
It is easy to show that. Or give a hint to the proof.

I invite my readers to give proofs to see if they differ from
my students, and also so that the next time someone needs to
reference this, they can point to this blog and attibute
it to some cute alias.

A student asked me if giving as a reference a blog site or
an unpublished paper on line is legit. I would say its more legit
then giving as a reference a paper that is not on-line.
A paper that is refereed but not online had a few people look at it closely.
A paper that is unrefereed but online might have a lot more people
look at it (then again, it might not). But since the reader can
access it, he or she might be able to
tell for himself or herself
whether the statement they need has been proven properly.