Matroide: differenze tra le versioni

Consideriamo, all'opposto, una situazione che non porta ad una matroide. Sia ''E'' l'insieme dei nodi di un grafo e chiamiamo insiemi di nodi indipendenti qualliquelli che possono essere colorati con non più di tre colori senza coincidenze fra nodi adiacenti. L'insieme vuoto soddisfa alla condizione e ogni sottoinsieme di nodi tricolorabile è tricolorabile; non vale invece la proprietà di scambio, in quanto si possono avere due sottografi massimali tricolorabili con diversi numeri di nodi, come mostrato nella figura alla destra.