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
    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

3

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.

enter image description here

  • 0
    We should I think also note that this is worst case scenario construction, because, for example, one can drop one of the vertices and add some other edges to the above graph. (Sometimes I forgot this) Thanks for the graphical content @Schulz.2018-05-29
2

Let V be the set of verticies of G. Let u be the vertex of maximum degree,Let A be the set of neighbours of u and Let B be the set of all neighbours of neighbours of u except u. since the distance between any 2 verticies is at most 2 therefore V-{u} is a subset of A U B. Since the maximum degree is <= 3 therefore $|A|<=3$ by a similar argument we knw that the number of neighbours(different from u) of neighbours of u is at most 2. Therefore |B| <= 2|A| threfore |V-{u}| <=|A U B| <= |A|+|B| <= 3|A| <= 9 therefore |V| <= 10

  • 0
    I just curios whether it is typo, or really a thing: You said "$u$ be *the* vertex of maximum degree...". Does is have to a unique vertex having the maximum degree, or you just choose one of the vertices having the maximum degree ?2018-05-29