# TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Übungen WS20/Beispiel 7

## Hilfreiches[edit | edit source]

## Lösungsvorschlag von Itf[edit | edit source]

For the first part: Let G=(V,E) be a Graph with at least as many edges as vertices ->

Assume that G has no cycles. From the lecture we know that a tree is a maximally acyclic graph, adding an edge leads to a cycle --> G is a forest/tree. For a tree, it holds that --> . This contradicts the previous statement .

For the second part: Show by induction Induction Step: k = 0 --> Graph has n - 0 = n connected components (one for each vertex)

k => k+1 (k>=0) Let G=(V,E) be a Graph with at least n-k components (|V| = n, |E| = k) Show that G'=(V,E') has at least n-(k+1) components (|V| = n, |E| = k+1)

Take G and add an arbitrary edge e={u,v} (Resulting in G')

Two Cases:

I: u and v are part of the same component, the number of components stays the same --> n-k >= n-k-1 OK

II: u and v are part of different components. The components are "merged" to one component (the other components stay untouched)
G' has one less component, therefore the number of components in n-k-1 OK

--Itf 07:52, 20. Okt. 2020 (CEST)