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

Aus VoWi
Zur Navigation springen Zur Suche springen

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!

Theory[Bearbeiten | Quelltext bearbeiten]

Solution[Bearbeiten | Quelltext bearbeiten]

2.a[Bearbeiten | Quelltext bearbeiten]

Lets assume that there are no people with the same number of neugbours, therefore we want to proof the existence of where no pair element of exists with

Note: I replace to make formulas easier readable.

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

Gaussian Sum formula

From the handshake Lemma we know that the sum of all degrees is .

Therefore 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:

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

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[Bearbeiten | Quelltext bearbeiten]

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

The number of Edges using the Hand Shaking Lemma:

Here we have our contradiction. In a simple graph the maximal degree of a node is . 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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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

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