Grafi e colorazioni. Una proposta laboratoriale per il liceo matematico

La matematica discreta ha assunto un ruolo importante negli ultimi decenni fornendo gli strumenti per affrontare temi di grande attualità quali la modellizzazione, il pensiero algoritmico, i processi decisionali. Inoltre, grazie al suo carattere talvolta eterogeneo e comunque aperto a varie connessioni con diverse aree della matematica (combinatoria, logica, algebra, geometria,…) si presta ad essere introdotta a vari livelli e in vari contesti del curriculum di uno studente. In questo articolo ci interessiamo ad alcuni aspetti della teoria dei grafi, una parte della matematica discreta, che possono essere oggetto di attività laboratoriali o di approfondimento in una scuola secondaria superiore. Si parte dall'analizzare il problema dei ponti di Königsberg, la cui soluzione viene fatta scoprire passo passo al lettore. Ad esso segue una parte relativa al problema delle colorazioni di una mappa (quanti colori servono per colorare una cartina geografica in modo che regioni confinanti non abbiano lo stesso colore?), con particolare riferimento al problema dei 4 e 6 colori