se realiza por inducción estructural basándose en la siguiente regla de inferencia: La prueba por inducción estructural consiste en demostrar que una proposición se cumple para todos los elementos mínimos del tipo, y que si la propiedad se cumple para todas las subestructuras de una cierta estructura S, entonces se debe cumplir también para S. Por ejemplo, si la estructura es una lista, normalmente se introduce el orden parcial '<' tal que L < M siempre que exista x tal que x::L=M Bajo este orden, la lista vacía [] es el único elemento mínimo.
Para demostrar esta propiedad, hace falta conocer las definiciones de las operaciones longitud y concatenar.
La proposición P(l) en este ejemplo es que EQ es verdadero cualquiera sea la lista L como valor del l. Se debe demostrar P(l) cualquiera sea la lista y para ello se utiliza inducción estructural sobre listas.
Primero se demuestra P([]), es decir EQ es cierto para cualquier lista M cuando L es [].
En este contraejemplo, el número de nodos internos difiere del número de hojas más uno, pero no puede ser el árbol más pequeño, dado que éste cumple con la propiedad.
Entonces, el contraejemplo mínimo tiene al menos una hoja cuyo ancestro es un nodo interno.
Al reemplazar ese nodo interno por el hermano de la hoja en el contraejemplo mínimo se obtiene un árbol más pequeño que también es un contraejemplo, lo que representa una contradicción.