Il numero di cappi in un grafo è uguale al numero di vertici con grado dispari?
No, questa affermazione non è corretta. Il numero di cappi in un grafo non è direttamente correlato al numero di vertici con grado dispari.
La confusione potrebbe derivare da una misinterpretazione di alcuni concetti fondamentali della teoria dei grafi.
Vediamo di chiarire questi concetti con esempi pratici per facilitarne la comprensione.
- Cappi: Un cappio (loop) è un arco che collega un vertice a se stesso. Ogni cappio aumenta di due il grado del vertice a cui è connesso, poiché in termini di grado, ogni estremità dell'arco contribuisce separatamente.
- Vertici con grado dispari: La parità del grado di un vertice (il numero totale di archi che lo collegano ad altri vertici, contando un cappio come due) può essere pari o dispari. Questo dipende dal numero totale di archi connessi a quel vertice, non solo dai cappi.
Il Teorema delle strette di mano (o Teorema della parità), uno dei fondamenti della teoria dei grafi, afferma che in qualsiasi grafo, il numero di vertici con grado dispari è sempre pari.
Questo teorema però non stabilisce una relazione diretta tra il numero di cappi e il numero di vertici con grado dispari.
Esempio
Ad esempio, consideriamo un grafo con un solo vertice e un cappio:
Qui abbiamo un solo vertice (A) con grado pari a 2 poiché il cappio conta come due.
Il grafo ha un numero dispari di cappi (1), ma non ha vertici con grado dispari. E già questo dimostra come l'affermazione iniziale sia falsa.
Facciamo un altro esempio pratico.
Prendiamo un grafo con tre vertici, dove due vertici (B e C) sono connessi da un arco e un vertice (A) ha un cappio.
Il vertice A con il cappio ha grado 2, mentre gli altri due vertici B e C hanno grado 1 perché sono connessi da un solo arco.
Quindi, nel grafo ci sono due vertici con grado dispari, ma solo un cappio. Anche in questo caso l'affermazione iniziale viene confutata.
In conclusione, il numero di cappi in un grafo non determina il numero di vertici con grado dispari.
Spero che questo esempio abbia aiutato a chiarire il malinteso.
