Consideriamo i grafi ad albero non orientati, ossia i grafi non orientati che non contengono maglie (cioè cammini chiusi). A destra sono rappresentati i possibili grafi ad albero non orientati con 2 nodi (uno) e con 3 nodi (tre). Quanti sono i grafi ad albero non orientati con 4 nodi, come quello in alto a sinistra? (quello in basso non è accettabile in quanto ha una maglia)

A sinistra sono elencati tutti e 16 i grafi ad albero non orientati con 4 nodi. Sono tutti i modi in cui possiamo congiungere quattro città (senza anelli, cioè senza la possibilità di partire da una città e ritornare nella stessa non invertendo la direzione di marcia).
Il tedesco Carl Borchardt (nel 1860) ha dimostrato che se i nodi sono N i grafi ad albero possibili sono N^N−2. Ciò concorda non quanto ora visto per N = 2, N = 3 e N = 4.

Qualcuno aggiunge a "grafi ad albero non orientati" l'aggettivo "completi", per precisare che tutti i punti sono direttamente o indirettamente collegati, ossia che non si considerano grafi "non connessi".

# Ecco come sono state realizzate le figure con R (vedi):
source("http://macosa.dima.unige.it/r.R")
BF=3; HF=3
PLANEww(0,11,0,11)    # usa PLANE(0,11,0,11) se vuoi  dedere la griglia
POINT(0,10,"black"); POINT(2,10,"black"); line(0,10, 2,10, "black")
POINT(0,8,"black"); POINT(2,8,"black"); POINT(1,6,"black"); polyl(c(0,2,1),c(8,8,6),"black")
POINT(3,8,"black"); POINT(5,8,"black"); POINT(4,6,"black"); polyl(c(3,4,5),c(8,6,8),"black")
POINT(6,8,"black"); POINT(8,8,"black"); POINT(7,6,"black"); polyl(c(8,6,7),c(8,8,6),"black")
#
PLANEww(0,11,0,11)
POINT(0,11,"black"); POINT(2,11,"black"); POINT(0,9,"black"); POINT(2,9,"black")
polyl(c(0,0,2,2),c(11,9,9,11),"black")
POINT(3,11,"black"); POINT(5,11,"black"); POINT(3,9,"black"); POINT(5,9,"black")
polyl(c(5,3,3,5),c(11,11,9,9),"black")
POINT(6,11,"black"); POINT(8,11,"black"); POINT(6,9,"black"); POINT(8,9,"black")
polyl(c(6,6,8,8),c(9,11,11,9),"black")
POINT(9,11,"black"); POINT(11,11,"black"); POINT(9,9,"black"); POINT(11,9,"black")
polyl(c(9,11,11,9),c(11,11,9,9),"black")
POINT(0,8,"black"); POINT(2,8,"black"); POINT(0,6,"black"); POINT(2,6,"black")
polyl(c(0,0,2,2),c(8,6,8,6),"black")
POINT(3,8,"black"); POINT(5,8,"black"); POINT(3,6,"black"); POINT(5,6,"black")
polyl(c(3,3,5,5),c(6,8,6,8),"black")
POINT(6,8,"black"); POINT(8,8,"black"); POINT(6,6,"black"); POINT(8,6,"black")
polyl(c(6,8,6,8),c(8,8,6,6),"black")
POINT(9,8,"black"); POINT(11,8,"black"); POINT(9,6,"black"); POINT(11,6,"black")
polyl(c(11,9,11,9),c(8,8,6,6),"black")
POINT(0,5,"black"); POINT(2,5,"black"); POINT(0,3,"black"); POINT(2,3,"black")
polyl(c(0,2,0,2),c(3,5,5,3),"black")
POINT(3,5,"black"); POINT(5,5,"black"); POINT(3,3,"black"); POINT(5,3,"black")
polyl(c(3,5,5,3),c(5,3,5,3),"black")
POINT(6,5,"black"); POINT(8,5,"black"); POINT(6,3,"black"); POINT(8,3,"black")
polyl(c(6,8,6,8),c(5,3,3,5),"black")
POINT(9,5,"black"); POINT(11,5,"black"); POINT(9,3,"black"); POINT(11,3,"black")
polyl(c(11,9,9,11),c(5,3,5,3),"black")
POINT(0,2,"black"); POINT(2,2,"black"); POINT(0,0,"black"); POINT(2,0,"black")
polyl(c(0,0,2,0,2),c(0,2,0,2,2),"black")
POINT(3,2,"black"); POINT(5,2,"black"); POINT(3,0,"black"); POINT(5,0,"black")
polyl(c(3,5,3,5,5),c(2,2,0,2,0),"black")
POINT(6,2,"black"); POINT(8,2,"black"); POINT(6,0,"black"); POINT(8,0,"black")
polyl(c(6,8,6,8,8),c(0,0,2,0,2),"black")
POINT(9,2,"black"); POINT(11,2,"black"); POINT(9,0,"black"); POINT(11,0,"black")
polyl(c(9,9,11,9,11),c(2,0,2,0,0),"black")