代做Compsci 225 Assignment 4 Semester 1, 2024代写留学生Matlab程序

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).