# Introduction to graph theory/Problems 2

## Problems 2: Lecture 6-10

### Planar Graphs

The n-dimensional Cube ${\displaystyle Q_{n}}$ or hypercube can be seen as a graph. Its nodes are the words of length ${\displaystyle n}$ over the alphabet ${\displaystyle \{0,1\}}$, or ${\displaystyle 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 ${\displaystyle Q_{n}}$ have? How many edges?
2. Describe the degrees of the nodes in ${\displaystyle Q_{n}}$.
3. Embed ${\displaystyle Q_{1},Q_{2},Q_{3}}$ and ${\displaystyle Q_{4}}$ into the plane - without intersections, if possible.
4. Embed ${\displaystyle 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 ${\displaystyle G}$ so that the resulting graph is planar.

1. Show that for a simple graph ${\displaystyle G}$ with ${\displaystyle n\geq 3}$ nodes and ${\displaystyle m}$ edges the following equation holds:
${\displaystyle skewness(G)\geq m-3n+6}$
1. Calculate the skewness for ${\displaystyle K_{3},K_{5},K_{3,3}}$

Trees

Show the equivalence of the following statements for a graph ${\displaystyle G}$ with ${\displaystyle n}$:

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