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

1) A simple undirected graph is called cubic if each of its vertices has degree 3.

• (a) Find a cubic graph with 6 vertices!
• (b) Is there a cubic graph with an odd number of vertices?
• (c) Prove that for all n ≥ 2 there exists a cubic graph with 2n vertices!

Theory

• Wikipedia: Cubic Graph
• Wikipedia: The Fundamental theorem of arithmetic (s17 Mathematik für Informatik)
• Handshaking lemma (s59 Mathematik für Informatik)

Solution

1.a

See Wikipedia example

1.b

$\sum _{v\in V}\Gamma (v)=2\cdot |E|$

according to the Handshaking lemma

The left side is known to some degree:

$\sum _{v\in V}3=2\cdot |E|$ as every vertex has a degree of 3

$(n\cdot 2+1)\cdot 3=2\cdot |E|$ as the number of vertices is an odd number

$2\mid 2\cdot |E|$ and $2\not \mid (n\cdot 2+1)\cdot 3$

The Fundamental theorem of arithmetic implies that the two sides are not the same and therefore no such graph exists.
($d\mid n$ means "Integer n is a divisible by an integer d", see: https://math.stackexchange.com/questions/135253/notation-for-is-divisible-by)
(The $\not \mid$ should be a "d not divides n")

1.c

Proof by induction:

• $n_{0}=2$:

The complete graph with 4-vertices (K4) is a cubic graph.

• $P(n)\implies P(n+1)$:

1. Take a "chain" of 3 vertices

2. Remove the edges connecting them

3. Connect the two new vertices as follows:

e.g $P(2)\implies P(3)$:

Formal notation and the proof why the first step is possible are left as an exercise for the reader.

Materialien

Neues Material hinzufügen

E

• example.png (details)

P

• pn implies pn plus 1.png (details)