# Introduction to graph theory/Problems 2

Jump to navigation
Jump to search

## Problems 2: Lecture 6-10

[edit | edit source]### Planar Graphs

[edit | edit source]The n-dimensional Cube or hypercube can be seen as a graph. Its nodes are the words of length over the alphabet , or . Two nodes are adjacent if and only if they differ in exactly one position.

- How many nodes does have? How many edges?
- Describe the degrees of the nodes in .
- Embed and into the plane - without intersections, if possible.
- Embed 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 so that the resulting graph is planar.

- Show that for a simple graph with nodes and edges the following equation holds:

- Calculate the skewness for

Trees

Show the equivalence of the following statements for a graph with :

- is a tree, i.e. is connected and has circle-free.
- is connected and has edges.
- is circle-free and has edges.