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\geq 3$ nodes and $m$ edges the following equation holds:

$skewness(G)\geq 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.