TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 6

6) Prove that a simple undirected graph G with n vertices and more than (n−1)(n−2)/2 is connected!

Theory

Note: I think this exercise has one little misstake. It should be:

... and more than (n−1)(n−2)/2 EDGES is connected!

Solution

Note: I'm not happy with my explaination on how the vertices should be split in two components, so if someone knows a better way I'm happy if you replace my one. :)

First we split the Vertices in two components, |V1|=j |V2|=k with j+k=n. (n = |V|)

We now want to have as much as possible edges in this two components without connecting them. So |E1| = j(j+1)/2; |E2| = k*(k+1)/2 and |E1| + |E2| should be max.

We substitute k with n-j: j(j+1)/2 + (n-j)*((n-j)+1)/2 = f(j) => should be max.

There is no maximum for this function, but f(j) is a parable with a minimum in k=n/2 (and j=n/2). So it means that a maximum for our interval would be the interval borders, means k=n-1; j=1 or j=n-1; k=1.

Now we know how we should split our Vertices in two components, so we can start calculating the maximum number of edges without connecting them. The number of edges in a complete component is |V|*(|V|-1)/2, therefore we have

|E1max| = (n-1)((n-1)-1)/2 = (n-1)(n-2)/2 |E2max| = 1*(1-1)/2 = 0

So the maximum number of edges without connecting the components is (n-1)(n-2)/2. If we want add an edge (as requested in the exercise description) it must connect the two components.

alternate Solution

we have a fully connected Graph $G'=(V',E')$ with $|V'|=n-1$

we can easily compute $|E'|={\frac {(n-1)(n-2)}{2}}$

If we now want to add a new vertice $v$, this vertice is not connected to any other vertice of $V'$. If we want to add even one edge $e$, then vertex $v$ will be connected to the rest of the vertices of $V'$, because $V'$ is allready fully connected and multiple edges are not allowed in simple graphs.

--Neroburner (Diskussion) 15:15, 12. Okt. 2013 (CEST)