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

Math 2070

Test 1

(1) You must complete the test BY YOURSELF. Acts of academic dishonesty will be subject to academic discipline.

(2) You are permitted to use your class notes, your textbook, and any of the material posted on UM Learn.  You are NOT permitted to use calculators, cellphones (other than for viewing/submitting the questions), personal music players, WiFi or cell en- abled devices, external websites (i.e.  you are only permitted to use UM Learn and Crowdmark), electronic dictionaries, or any similar aids/devices.

(3) You may use any result from the lectures so far, any result from the tutorial worksheets, any result from the assignments, and any results from sections 1.1-1.9, 1.12.1, and 2.1-

2.3 in the textbook (unless you are specifically asked to prove it).  You may not use any other graph theory results.

(4) Unless instructed otherwise, you must show work (calculations, explanations) to receive full credit. Answers that are not legible may not receive marks.

(5) You have until 2:15pm to complete and submit your solutions. Note that you need to submit (that means you have clicked Submit for evaluation”) BEFORE 2:15pm.

(6) If you have any questions or uploading problems during the test,  Mike will be on Zoom (the normal lecture link).  You are not required to be on Zoom, but it would be  a good idea just in case there is  a problem  (especially if your running out of time  and you’re  having  uploading problems).   Alternatively,  you  may  email  Mike ([email protected]), but Zoom will likely be faster.

(7) Relax. This test does not measure your worth as a human being.

 

Problem  1.   (5 marks) Let G  =  (V, E) be a graph such that  IV I  >  2.   Prove that if IV I - 2

 

Solution:  Suppose, for a contradiction, that G has least three components.  Let X be a component of G with the minimum number of vertices and let x e V (X). Then IV (X)I s 

and

IV I              IV I - 3       IV I - 2

3                  3               3

which is a contradiction. Thus G has at most two components, as required.                     

 

Problem 2. (5 marks) Is the sequence (6, 5, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1) graphical. If it is graph- ical, draw a realization. If it is not graphical, explain why not.

Solution:  By the Havel-Hakimi Theorem, the sequence (6, 5, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1) if and only if the sequence

(4, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1)

is graphical. By another application of the Havel-Hakimi Theorem, the sequence (4, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1) is graphical if and only if the sequence

(3, 3, 3, 3, 2, 2, 2, 2, 1, 1)

is graphical. We see that (3, 3, 3, 3, 2, 2, 2, 2, 1, 1) is graphical because it is the degree sequence of the graph K4  u C4  u K2 .  Therefore the sequence (6, 5, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1) is indeed graphical.

A realization of (6, 5, 4, 4, 4, 4, 4, 3, 3, 3, 1, 1) is the following graph:

 

 

NOTE: There are other possible realizations.

 

 


Problem 3.  (6 marks) For integers i, k, and n where 0 s i s k s n, define G(n, k, i) as the graph whose vertex set is the set of k-element subsets of [n] and two vertices S and T are adjacent if and only if IS n T I = i.

(a) Draw the graph G(4, 2, 1).

Solution: The graph G(4, 2, 1) is as follows:

{1, 2}

{1, 3}

 

 

 

 

 

 

 

 

{1, 4}

 

{2, 3}

 

(b) Determine the number of edges in G(n, k, 1).

Solution: Let X be a k-subset of [n]. For each v e X, there are  other k-subsets Y of [n] such that X n Y = {v}.  Therefore, degG(n,k,1)(X) = k  for each X e V (G(n, k, 1)). Since IV (G(n, k, 1))I = k(n)、, the Handshake Lemma yields

IE(G(n, k, 1))I =                     degG(n,k,1)(X)

XeV (G(n,k,1))

 .   


 

 

Problem 4.  (9 marks) Are the following pairs of graphs isomorphic? If so, write down an isomorphism (You don’t need to prove it’s an isomorphism). If not, give a reason why not.


(a)  G and H

3

G

5


a

 

f

 

e

 

d

 

Solution: Not isomorphic: The graph H is has a 3-cycle, but G does not.

 

(b) X and Y

1

 

 

X

 

 

5

 

 

 

2

 

 

 

 

f 6

d

e

 

 

 

 

 

Y


Solution:  Isomorphic:  An isomorphism is f(1) = f , f(2) = e, f(3) = d, f(4) = a, f(5) = c, and f(6) = b (there are other possibilities).

 

(c) Γ and Π

 

3

Γ      1

4

a

 

c

 

e

 

 

 

 

b

 

d     Π

 

f

 

Solution: Not isomorphic: We see that ∆(Γ) = 3 while ∆(Π) = 4.


 

Problem 5.  (5 marks) A graph G = (V, E) is 事。佐á2≠〉扛(4〉扛扛卜4≠卜| if for all u, v e V , there is a Hamilton uv-path in G.  Show that if G = (V, E) is Hamilton-connected and IV I > 3, then G is Hamiltonian.

Solution:  Let G = (V, E) be Hamilton-connected graph such that IV I > 3.  Let xy e E . Since G is Hamilton-connected, there is a Hamilton xy-path P in G.  Furthermore, since IV I > 3, P does not contain the edge xy . Thus, P together with the edge xy is a Hamilton

cycle in G, and G is Hamiltonian, as required.

 

 

Problem 6.  (5 marks) Let G be a connected Eulerian graph with at least three vertices. Show that G has at least three vertices of the same degree.

Solution:  Let G = (V, E) be a connected Eulerian graph such that IV I > 3.  Since G is connected and Eulerian, for all x e V , we have

degG (x) e {2, 4, 6, . . . , N}


where

N = _

 

 

if IV I is odd

if IV I is even

Therefore, there are at most  _ ) possibilities for degG (x). Since G has IV I vertices, the

Pigeonhole Principle tells us that there are at least

 - = 3

vertices of the same degree, as required.