Introduction to graph theory/Problems 2

Problems 2: Lecture 6-10

edit

Planar Graphs

edit

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.

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

  1. Show that for a simple graph   with   nodes and   edges the following equation holds:
 
  1. Calculate the skewness for  

Trees

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

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