Introduction to graph theory/Problems 2

Problems 2: Lecture 6-10

Planar Graphs

The n-dimensional Cube $Q_n$ or hypercube can be seen as a graph. Its nodes are the words of length $n$ over the alphabet $\{0,1\}$, or $V(Q_n)=\{0,1{\}}^n$. Two nodes are adjacent if and only if they differ in exactly one position.

1. How many nodes does $Q_n$ have? How many edges?
2. Describe the degrees of the nodes in $Q_n$.
3. Embed $Q_1,Q_2,Q_3$ and $Q_4$ into the plane - without intersections, if possible.
4. Embed $Q_4$ intersection-free on the surface of a torus.

Skewness

The skewness of a graph is the minimum number of edges which have to be removed from $G$ so that the resulting graph is planar.

1. Show that for a simple graph $G$ with $n\ge 3$ nodes and $m$ edges the following equation holds:

$skewness(G)\ge m-3n+6$

1. Calculate the skewness for $K_3,K_5,K_{3,3}$

Trees

Show the equivalence of the following statements for a graph $G$ with $n$:

1. $G$ is a tree, i.e. $G$ is connected and has circle-free.
2. $G$ is connected and has $n-1$ edges.
3. $G$ is circle-free and has $n-1$ edges.