Compsci 225 Assignment 4 Semester 1, 2024

发布时间：2024-05-29

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Compsci 225

Assignment 4

Semester 1, 2024

Due: Monday 27 May by 23:59

1. (5 + 4 + 4 marks)

(a) A degree sequence of a graph G = (V, E) is a sequence of numbers (n0 , n1 , . . .), where ni denotes the number of vertices in G of degree exactly i. Prove that if G = (V, E) and H = (V′ , E′ ) are isomorphic, then their degree sequences are identical.

Note: You cannot just say “it’s the same graph, therefore degree sequences are the same”. You need to use the definition of isomorphism, that is, G and H are isomorphic if there exists a bijection f : V → V′ such that {v, w} ∈ E ⇔ {f(v), f(w)} ∈ E′ .

(b) Are the following two graphs isomorphic? If no, explain why not. If yes, define a bijection f : V → V′ which proves it.

(c) Are the following two graphs isomorphic? If no, explain why not. If yes, define a function f : V → V′ which proves it.

2. (6 marks)

Let G = (V, E) be a graph. Define a relation R on V as follows: aRb if and only if there is a walk between a and b in G. Show that R is an equivalence relation. Note: A single vertex is also a walk.

(Equivalence classes of this relation are what we call connected components of the graph G.)

3. (5 marks)

Let G = (V, E) be a graph with n vertices and δ(G) ≥ n/2. Prove that G is connected.

Hint: Show that for every two vertices v, w ∈ V which are not adjacent, there exists u ∈ V such that v,u,w is a path.

4. (4 + 4 marks)

Let G = (V, E) be a connected graph. In this exercise we prove that every two longest paths in G have a vertex in common. Suppose, towards a contradiction, that there exists two longest paths P = p1 , p2 ,..., pk and Q = q1 , q2 ,...,qk which are disjoint, that is {p1 ,..., pk}∩ {q1 ,...,qk} = ∅ .

(a) Show that there exists a path Z from some vertex p ∈ P to some vertex in q ∈ Q, which does not contain any other vertex from (P \ {p}) ∪ (Q \ {q}).

(b) Use paths P , Q, and Z to construct a path of length longer than k, that is, longer than P and Q. This contradicts the assumption that there are no paths in G longer than P and Q.

Note: In proving (b), you can use (a) even if you did not prove it.

5. (5 marks)

Prove that Qn contains a Hamilton path. In case you do not manage to do that, specify a Hamilton path of Q4 as a list of vertices (2 marks).

Hint: Prove the claim by induction on n. There is no recipe here to follow, and no result that can help you in proving this. What is required is a good old trial and error and some thinking.

6. (5 marks)

Consider a graph G = (V, E) where V = {1,..., n}×{1,..., n} and vertices (x,y) and (x′ , y′ ) are adjacent if and only if either x = x′ and |y − y′ | = 1, or |x − x′ | = 1 and y = y′ . Describe a partition V = V1 ∪ V2 which proves that G is bipartite.

Hint: Draw the graph for n = 4.

7. (4 + 4 marks)

Let G = (V, E) be a graph with at least 2 vertices. The goal of this exercise is to show there exists E′ ⊆ E of size |E′ | ≥ |E|/2 such that G′ = (V, E′ ) is bipartite. In other words, every graph contains a large bipartite graph.

Consider the following process: Start with an arbitrary partition V = V1 ∪ V2 such that |V1| , |V2| ≥ 1. Repeat: if there exists a vertex v ∈ V1 such that v has more neighbours in V1 than V2, move v from V1 to V2; or, if there exists a vertex v ∈ V2 such that v has more neighbours in V2 than V1, move v from V2 to V1. When there is no vertex satisfying either of the conditions, terminate the procedure.

(a) Show that the number of edges with one endpoint in V1 and the other in V2 increases after every iteration.

(b) After the procedure has finished, take E′ ⊆ E to be the set of all edges between V1 and V2 . Then G′ = (V, E′ ) is clearly bipartite. Show that |E′ | ≥ |E|/2.

Note: Part (a) implies that the procedure eventually terminates. You can prove (b) without proving (a).