Graph Theory - Graph with degree at most 3 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.

I follow the ideas of Thomas Andrews. Suppose that $v$ is some vertex and consider the Breadth-First-Search tree rooted at $v$. In this tree $v$ has at most $3$ childrean $v_1,v_2,v_3$, and each of the $v_i$ has at most $2$ childrean. There are no deeper nodes in this tree due to the disance requirement. Hence you have $1$ node in the first level, $3$ nodes in the second level and $3*2=6$ nodes in the third level of the BFS tree. In total $1+3+6=10$ nodes.
As mentioned in the comments by Angela Richardson the Petersen graph is a 10 vertex graph that has this property. The following picture depicts the graph and the BFS tree as (blue edges) for the central node.

