Introduction to graph theory/Problems 2

From Wikiversity
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.

  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.


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


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.