1 Graph Basics
In the first few parts, you will be answering questions on the following graph G.
(a) What are the vertex and edge sets V and E for graph G?
(b) Which vertex has the highest in-degree? Which vertex has the lowest in-degree? Which vertices have the same in-degree and out-degree?
(c) What are the paths from vertex B to F, assuming no vertex is visited twice? Which one is the shortest path?
(d) Which of the following are cycles in G?
i. (B,C),(C,D),(D,B)
ii. (F,G),(G,F)
iii. (A,B),(B,C),(C,D),(D,B) iv. (B,C),(C,D),(D,H),(H,G),(G,F),(F,E),(E,D),(D,B)
(e) Which of the following are walks in G?
i. (E,G)
ii. (E,G),(G,F)
iii. (F,G),(G,F)
iv. (A,B),(B,C),(C,D),(H,G)
v. (E,G),(G,F),(F,G),(G,C)
vi. (E,D),(D,B),(B,E),(E,D),(D,H),(H,G),(G,F)
(f) Which of the following are tours in G?
i. (E,G)
ii. (E,G),(G,F)
iii. (F,G),(G,F)
iv. (E,D),(D,B),(B,E),(E,D),(D,H),(H,G),(G,F)
In the following three parts, let’s consider a general undirected graph G with n vertices (n ≥ 3).
(g) True/False: If each vertex of G has degree at most 1, then G does not have a cycle.
(h) True/False: If each vertex of G has degree at least 2, then G has a cycle.
(i) True/False: If each vertex of G has degree at most 2, then G is not connected.
2 Odd Degree Vertices
Claim: Let G =(V,E) be an undirected graph. The number of vertices of G that have odd degree is even.
Prove the claim above using:
(i) Direct proof (e.g., counting the number of edges in G). Hint: in lecture, we proved that ∑v∈V degv = 2|E|.
(ii) Induction on m = |E| (number of edges)
(iii) Induction on n = |V| (number of vertices)
(iv) Well-ordering principle (Hint: Try rephrasing one of the induction proofs.)
3 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.
