1
$\begingroup$

Can somebody explain why there cannot be any triangles or squares in a Moore graph with diameter 2? This was stated without proof in my class.

$\endgroup$
1
$\begingroup$

I don't know which definition you're using, but on Wikipedia, a useful one is that a Moore graph is a graph $G$ of diameter $k$ and girth $2k + 1$.

That means if $k = 2$, then the smallest cycle in $G$ has $5$ vertices. Having a triangle or a square would contradict that.

$\endgroup$
2
  • $\begingroup$ It says that this is an equivalent definition to the one with the sum (which I a was given). Can you provide a proof that the two are equivalent? $\endgroup$ – vounoo May 4 '15 at 10:57
  • 2
    $\begingroup$ Actually no, I couldn't prove it myself nor find the original proof. Apparently it's in the paper "There is no irregular Moore graph" by R. Singleton (1968), but I could not find the paper online. I'll keep looking a bit. $\endgroup$ – Manuel Lafond May 5 '15 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.