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.

How many nodes does $Q_{n}$ have? How many edges?
Describe the degrees of the nodes in $Q_{n}$ .
Embed $Q_{1}, Q_{2}, Q_{3}$ and $Q_{4}$ into the plane - without intersections, if possible.
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.

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

s k e w n e s s (G) \geq m - 3 n + 6

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

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