Demostrando cada árbol tiene más de un perfecto maridaje

Question

En el intento de probar que cada árbol, T, tiene más de una perfecta coincidencia, me encontré con esta idea:

 Since the matchings are perfect, each vertex has degree 0 or 2 in the symmetric     
 difference, so every component is an isolated vertex or a cycle.

¿Por qué es esto cierto? ¿Por qué es cierto que a partir de cada vértice es de grado 0 o de grado 2, entonces todos los componentes están aislados o de un ciclo?

Answer 1

En primer lugar, ¿por qué la afirmación es verdadera. Tomar cualquier vértice. Si coincide con el mismo vértice, tanto en perfecta coincidencia, entonces tenía el grado cero de la diferencia simétrica. De lo contrario no tiene grado dos.

Segundo, después de la eliminación de todos los aislados de los vértices de la diferencia simétrica, todos los vértices tienen grado dos. Tome cualquier vértice y siga sus dos bordes. Lo que se obtiene es un crecimiento de la ruta que finalmente cerró un ciclo ya que la gráfica es finito.

Dado que los árboles no tienen ciclos, esto implica que cualquiera de los dos perfecto maridaje son iguales, por la que consiste su diferencia simétrica.

Una diferente de la prueba es por inducción. La idea es que cada una de las hojas debe ser compatible para su único vecino.

Answer 2

Ya que cada árbol de dos o más vértices es de dos cromática. Árbol con incluso no de los vértices tienen el perfecto maridaje como todos los vértices con el mismo color pueden ser agrupados y un juego que se pueden establecer entre dos grupos. Pero cualquier árbol con impar de vértices tendrá ninguna perfecta coincidencia por razones obvias. De ahí resultó.