Aufgabe:
Beweise: ein Kreisfreier Graph G=(V,E) mit |E| = |V|-1 ist ein Baum.
Es fehlt noch zu zeigen dass G zusammenhängend ist.
Beweis über vollst. Induktion:
Sei G=(V,E) mit |E|=n und |V| = n+1 (wobei E die anz der Kanten und V die anz der Knoten ist) ein Kreisfreier Graph für den |E|=|V|-1 gilt.
Ind: Anfang: n = 1, Der Graph G=(V,E) (|E|=1, |V|=2) mit 2 Knoten und einer Kante ist Kreisfrei und zusammenhängend und somit ein Baum.
Ind: Ann. Sei die Behauptung richtig für alle Graphen mit |E|<=n, |V|<=n+1
IS: Sei G=(V,E) ein Kreisfreier Graph mit |E| = n+1 und |V|=n+2. Da der Graph kreisfrei ist und |E|<= |V| gilt muss es einen Knoten v mit grad 1 geben. Entferne die Kante e von v mit v und erzeuge damit den Graphen G', nach der Ind Ann. ist G' ein Baum da er kreisfrei und zusammenhängend ist, wenn nun e und v zu G' hinzugefügt werden, erhält man wieder G. G ist auch ein Baum da das hinzufügen von e und v keinen Kreis entstehen lassen können und der Graph zusammenhängend bleibt.
wäre der Beweis über Induktion so richtig?
mein zweiter Ansatz:
Beweis durch widerspruch:
Angenommen G ist kein Baum, dann muss G aus mehreren Komponenten bestehen da G schon Kreisfrei ist und |E| = |V|-1 gilt.Einen solchen Graph G kann es nicht geben da er aus mehreren Komponenten bestehen müsste und somit |V| -|E| >=2 gelten müsste, dies kann aber nicht gelten da |E| = |V|-1 gilt und der Graph Kreisfrei ist -> widerspruch.
