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

Show that a graph with at least as many edges as vertices contains a cycle. Show that a graph with n vertices and k edges has at least n-k connected components.

Lösungsvorschlag von Itf

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

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 $|V|=|E|+1$ --> $|V|>|E|$. This contradicts the previous statement $|E|>=|V|$.

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)