Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 tgat G has at most 10 vertices, and construct such a graph with 10 vertices.

share|improve this question
    
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? –  Thomas Andrews Nov 7 '12 at 14:49
    
The Peterson graph is such a 10 vertex graph. en.wikipedia.org/wiki/… –  Angela Richardson Nov 7 '12 at 14:57
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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