Teoría de grafos - Grafo de grado máximo 3

Question

Tengo una pregunta de teoría de grafos/combinatoria con la que me cuesta mucho trabajo, y agradecería algo de ayuda. La pregunta dice:

Supongamos que $G$ es un grafo tal que cada vértice tiene grado como máximo 3, y el camino más corto entre dos vértices cualesquiera tiene longitud como máximo 2. Demuestre que $G$ tiene como máximo 10 vértices, y construye un grafo de este tipo con 10 vértices.

Answer 1

Sigo las ideas de Thomas Andrews. Supongamos que $v$ es algún vértice y considere el árbol de búsqueda de amplitud en primer lugar rooteado en $v$ . En este árbol $v$ tiene como máximo $3$ infantil $v_1,v_2,v_3$ y cada uno de los $v_i$ tiene como máximo $2$ childrean. No hay nodos más profundos en este árbol debido al requisito de desancia. Por lo tanto, tiene $1$ nodo en el primer nivel, $3$ nodos en el segundo nivel y $3*2=6$ nodos en el tercer nivel del árbol BFS. En total $1+3+6=10$ nodos.

Como se menciona en los comentarios de Angela Richardson, el grafo de Petersen es un grafo de 10 vértices que tiene esta propiedad. La siguiente imagen representa el gráfico y el árbol BFS como (aristas azules) para el nodo central.

Answer 2

Sea V el conjunto de vértices de G. Sea u el vértice de máximo grado, sea A el conjunto de vecinos de u y sea B el conjunto de todos los vecinos de los vecinos de u excepto u. Como la distancia entre 2 vértices cualesquiera es como máximo 2, V-{u} es un subconjunto de A U B. Como el grado máximo es <= 3, por tanto $|A|<=3$ por un argumento similar sabemos que el número de vecinos (diferentes de u) de los vecinos de u es como máximo 2. Por lo tanto |B| <= 2|A| threfore |V-{u}| <=|A U B| <= |A|+|B| <= 3|A| <= 9 por lo tanto |V| <= 10