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

Compute the closure of the following graph:

## Lösungsvorschlag

Closure: Given a Graph ${\displaystyle G=(V,E),\forall v,w\in V}$ with ${\displaystyle d(v)+d(w)>=|V|}$ add the edge (v,w) to E[/itex]

Write down all possible edges/vertex pairs (which are not yet part of the graph). Then check the formula above for each of these vertex pairs. If the sum of the degrees is larger than the number of vertices, add the edge, and restart the comparison for those pairs, where one of the vertices has now a higher degree.
Example:

Possible pairs/edges: (v1, v3) (v1, v4) (v1, v6) (v1, v7) (v2, v4) (v2, v5) (v2, v7) (v3, v5) (v3, v6) (v4, v5) (v4, v7) (v5, v7)
Check edges, e.g. for (v3, v6) the formula holds --> add the edge to the graph
Possible pairs/edges: (v1, v3) (v1, v4) (v1, v6) (v1, v7) (v2, v4) (v2, v5) (v2, v7) (v3, v5) (v3, v6) (v4, v5) (v4, v7) (v5, v7)
Check edges (recheck pairs where one of the vertices is v3 or v6): (v1, v6) --> add the edge to the graph
etc....