1 Touring Hypercube
In the lecture, you have seen that if G is a hypercube of dimension n, then
• The vertices of G are the binary strings of length n.
• u and v are connected by an edge if they differ in exactly one bit location.
A Hamiltonian tour of a graph is a sequence of vertices v0,v1,...,vk such that:
• Each vertex appears exactly once in the sequence.
• Each pair of consecutive vertices is connected by an edge.
• v0 and vk are connected by an edge.
(a) Show that a hypercube has an Eulerian tour if and only if n is even.
(b) Show that every hypercube has a Hamiltonian tour.
2 Trees
Recall that a tree is a connected acyclic graph (graph without cycles). In the note, we presented a few other definitions of a tree, and in this problem, we will prove two fundamental properties of a tree, and derive two definitions of a tree we learned from the note based on these properties. Let’s start with the properties:
(a) Prove that any pair of vertices in a tree are connected by exactly one (simple) path.
CS 70, Fall 2018, DIS 3A 1
(b) Prove that adding any edge (not already in the graph) between two vertices of a tree creates a simple cycle.
Now you will show that if a graph satisfies this property then it must be a tree:
(c) Prove that if the graph has no simple cycles and has the property that the addition of any single edge (not already in the graph) will create a simple cycle, then the graph is a tree.
3 Planarity
Consider graphs with the property T: For every three distinct vertices v1,v2,v3 of graph G, there are at least two edges among them. Prove that if G is a graph on ≥ 7 vertices, and G has property T, then G is nonplanar.
