5
$\begingroup$

I've got a graph theory/combinatorics question that I'm really struggling with, and would appreciate some help. The question says:

Suppose $G$ is a graph such that every vertex has degree at most 3, and the shortest path between any two vertices has length at most 2. Show that $G$ has at most 10 vertices, and construct such a graph with 10 vertices.

  • 0
    Fix any node $x\in G$. How many nodes can be connected to $x$? So how many distinct nodes can be one or two edges away?2012-11-07
  • 0
    The Peterson graph is such a 10 vertex graph. http://en.wikipedia.org/wiki/Petersen_graph#CITEREFHoffmanSingleton19602012-11-07
  • 0
    You can construct such a graph with degrees $d=2,3,7$ each on $d^2+1$ vertices. If you can construct one with $d=57$ on $3250$ vertices or prove it's impossible you will have solved a famous open problem. These would all be Moore graphs https://en.wikipedia.org/wiki/Moore_graph2018-05-29

2 Answers 2