Número de vértices de grado n no conectados a vértices de grado 1

Question

Imagina un árbol compuesto solo de vértices de grado 1 y vértices de grado$n$.

Deje que$m$ sea el número de vértices de grado 1 y$\frac{m-2}{n-2}$ sea el número de$n$ - vértices del árbol.

¿Cómo puedo encontrar el número de vértices no conectados a un vértice de grado 1? Es decir, el número de$n$ - vértices conectados solo a otros$n$ - vértices.

Answer 1

Usted no puede, al menos no desde el grado de secuencia solo. Considere la posibilidad de un árbol de $T_1$ donde nodo es la raíz de sus vecinos son B,C,y D, y a su vez B,C y D tienen 2 hojas niños cada uno. A continuación, $T_1$ tiene 4 vértices de grado 3, es decir $A,B,C$ $D$--y 6 vértices de grado 1, y exactamente un vértice NO está conectado a un vértice de grado 1, es decir A.

Consideremos ahora otro árbol $T_2$ donde los nodos se $A,B,C$,e $D$ formar un camino, donde los nodos a es adyacente a los nodos de $E$ y $F$, $B$ es adyacente a $G$, $C$ a $H$, e $D$$I$$J$. [Así, en $T_2$ nodos $A,B,C,D$ todos tienen un grado exactamente 3, mientras que los nodos de $E$ a través de $J$ tienen un grado exactamente 1.] A continuación, $T_2$ también tiene 4 vértices de grado 3 y 6 vértices de grado 1, pero no el vértice no está conectado a un vértice de grado 1

T1:  L--B--A--D--L     T2:   E--A--B--C--D--J
       /   |   \                |  |  |  |
      L    C    L               F  G  H  I
          / \
         L   L

Answer 2

Un árbol con$k$ vértices tiene$k-1$ bordes.

En el otro lado, el número de bordes en un gráfico simple con$m$ vértices de grado$1$ y$\frac{m-2}{n-2}$ vértices de grado$n$ es$\frac{1}{2}(m+n(\frac{m-2}{n-2}-m)).$

Resolver$\frac{m-2}{n-2}-1=\frac{1}{2}(m+n(\frac{m-2}{n-2}-m)),$ obtenemos$m=0$ o$n=2.$ Ninguno de ellos es conveniente y, por lo tanto, tal árbol no existe.

COMENTARIO AGREGADO DESPUÉS DE SU EDICIÓN:

Con$\frac{m-2}{n-2}$ vértices de grado$n$, resolverás$\frac{m-2}{n-2}-1=\frac{1}{2}(m+n(\frac{m-2}{n-2})),$ lo que lleva a$m=0$ otra vez.