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

MATH 3V03 Fall 2021 - Term Test 2

 

1.  [10 pts] For each of the following questions, if possible, give an example of a finite simple graph with the given properties. Briefly explain why the properties are satisfied, or explain why such a graph doesn’t exist:

 

a) Has 5 vertices, 6 edges, and girth g = 4.

 

 


b) Is a 3-partite graph with chromatic number χ = 3.

 

 

 

c) Has a planar drawing with 3 regions, 6 vertices, and 7 edges.

 

 

 

d) Is a 4-cage and has a decomposition into cycles.


 

 

 

2. Consider the multigraph S pictured below:

 

H

G

m                             b           B

 

F                             A                             C

k                                           i

E                             D

j

 

a) [4 pts] Give an example of walk which is not a trail, and an example of circuit which is not a cycle. Each should use at least 4 edges. Write your answer as an alternating sequence of vertices and edges, and briefly explain why each example satisfies the given properties.

 

 

b) [3 pts] Does S contain an Eulerian trail? If so, explain why. If not, then what is the fewest number of edges that need to be added to S so that an Eulerian trail does exist?

 

 

c) [3pts] Prove that S does not have a decomposition into Hamilton paths.


 

 

3. Let HB  be the following bipartite graph:

 

 

 


A

 

E


B

 

F



 

 

 

 

 


 

 

a) [4 pts] Let M be the matching defined by M = {AF,BG}.  Find an M-augmenting path between C and D, and use it to construct a maximal matching from M. Be sure to briefly explain why your chosen path is M-augmenting.

 

 

b) [3 pts] Find a largest graph on 8 vertices which is bipartite and contains HB  as a subgraph.


 

 

 

 

4. The math department decides to host a conference and needs to choose a list of speakers. The organizers can’t decide whether to invite speakers who have joint research together, or to invite speakers who have never worked together (to promote networking). To keep their options open, they would like to guarantee that any list of speakers either contains a group of 4 people who have mutually never worked together, or contains a group of 4 people who have mutually worked together.

 

a) [1 pt] Explain why the organizers will need to invite at least r(4, 4) many speakers to guarantee these conditions (here r(a,b) is a Ramsey number).

 

 

 

 

b) [4 pts] Using that r(4, 5) = 25, r(3, 5) = 14 and r(3, 4) = 9, prove that 11 ≤ r(4, 4) ≤ 18.



 

5. Let G be a 5-regular simple graph with edge chromatic number χ′ (G) = 6.

 

(a) [3 pts] Show that G is not a maximal planar graph if |V(G)|  12.

 

 

 

 

(b)  [5  pts] Show that it is not possible for G to contain two Hamilton cycles H1  and H2  such that E(H1) ∩ E(H2) = ∅. (Hint: Towards a contradiction, construct a proper edge-coloring with 5 colors.)