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

2) Use a suitable graph theoretical model to solve the following problems:

• (a) Show that in every city at least two of its inhabitants have the same number of neighbours!
• (b) 7 friends want to send postcards according to the following rules:
  • (i) Each person sends and receives exactly 3 cards.
  • (ii) Each one receives only cards from those to whom he or she sent a card and vice versa. Tell how this can be done or prove that this is impossible!

Solution

2.a

Lets assume that there are no people with the same number of neugbours, therefore we want to proof the existence of $G(V,E)$ where no pair $v1≠v2$ element of $V$ exists with $d(v1)=d(v2)$

Note: I replace $|V|=n$ to make formulas easier readable.

As all Degrees should be different by our initial definition the minimum degree for n vertizes is:

$1+2+3+\mathrm{...}+n=n\cdot \frac{n+1}{2}$ $\to$ Gaussian Sum formula

From the handshake Lemma we know that the sum of all degrees is $2\cdot |E|$.

Therefore $|E|=n\cdot (n+1)$ is our minimal number of edges we need to construct the graph.

Now we want to know the maximum number of edges possible in a simple graph. So we pick all pairs vi, vj from V. This can be calculated as follows:

All possibilities to take 2 elements from n vertizes: $\left(\begin{array}{c}n\\ 2\end{array}\right)=\frac{n}{1}\cdot \frac{n-1}{2}=n\cdot \frac{n-1}{2}$

Now the minimal number of edges we need to constuct G must be smaller or equal to the maximum of possible edlges in a graph $\to$ $n\cdot (n+1)\le n\cdot \frac{n-1}{2}$

You can now solve this relation and see that it is impossible for n>0, therefore it is impossible that our assumed graph G can exist.

Note: I think it can also be proved by induction, but this is fairly simple as well. :)

2.a alternate

Same assumptions as above. Simple graph (everyone has a neighbour, noone is its own neighbour, no multiple edges). Lets assume there is a graph with $\mathrm{\forall }{v}_1,v_2\in V:d(v_1)\ne d(v_2)$

The number of Edges using the Hand Shaking Lemma: $\sum _{v\in V}d(v)=1+2+\dots +n$

Here we have our contradiction. In a simple graph the maximal degree of a node is $d(v)=n-1$. This implies that at least two nodes have to have the same number of neighbours. --NeroBurner (Diskussion) 09:35, 16. Okt. 2013 (CEST)

2.b

As the letters always go in both directions (by definition ii), we can replace this directed edges with one undirected edge. Then we have an undirected cubic graph with 7 vertices and d(v) = 3 for all v element of V. Now this is exactly what we disproved in Sample 1b.

2.b addition

disproved in 1.b. Only possible when we allow loops

--NeroBurner (Diskussion) 09:26, 16. Okt. 2013 (CEST)