grafi

[Thomas]

Salve... sto leggendo un pò di "graph theory" di Reinhard Diestel per vari motivi... vorrei proporvi due facili questioni, la prima l'ho inventata io la seconda vorrei vedere una vostra dimostrazione. Avviso che per quanto possano essere elementari nn consiglio di "provarci" a che nn conosce le elementari definizioni: i problemi non sono difficili ma usano risultati noti. Non so perchè ma sulle dimostrazioni con i grafi planari tendo a distinguere il caso in cui il grafo sia 2-connesso ed in cui un risultato noto mi garantisce che le frontiere di ogni faccia sono un ciclo e poi cerco di ricondurmi a questo caso per il risultato generico. Come prototipo per vedere cosa fareste voi posto il problema 2:

1) (mio, quindi magari sbagliato) - mostrare che un grafo planare con n vertici e $m>3n-11$ vertici è per forza 2-edge-connected.

2) mostrare che se un grafo planare possiede girth (definita come la lunghezza del ciclo più breve) g, m spigoli ed n vertici, vale:

$m \le (g)/(g-2)(n-2)$

[Nidhogg]

Per il primo quesito con m intendi gli spigoli?

Per il secondo prova ad utilizzare sia il fatto che dato $Gamma = (V,E)$ multigrafo si ha $\sum_{v in V} d_{Gamma}(v) = 2|E|$ (sostituendo i vertici con le facce) e inoltre utilizzando il teorema di Eulero...


Saluti, Ermanno.