2602 Homework #7-#12

MATH 2602 Homework #7-#12
Due Wednesday Oct 1 - Nov 5, covering the material of Exam 2 on Nov 5

Core : Book problems: Section 5.2 on page 167 problems 1b-1d, 3, 12a-12c, 20a-20b.
Section 5.3 on page 174 problems 2, 8, 13a.
Section 5.4 on page 181 problems 1a-1c.

Supplementary: (a) For n≥0, give a recurrence relation for the number an of ways to fill a 2×n chessboard using non-overlapping *dimers*, or tiles of dimension 2×1.
For example, a₄ = 5 since there are five such tilings (see picture)

You may assume a₀ = 1.
(b) The sequence a₀,a₁,a₂,... is a well-known sequence. What is it?

Core : Book problems: Review exercises for Chapter 5, page 183 problems 25, 29.
Section 8.1 on page 252 problems 8, 9, 10, 13.
Section 8.2 on page 264 problems 1, 2, 4, 5, 7a-7b, 7d, 9.

Core : Book problems: Section 8.2 on page 264 problems 13b, 27a-27b.
Section 8.3 on page 275 problems 1b, 8, 10a-10b, 14.
Section 8.4 on page 279 problems 2c, 7a.
Chapter 8 review problems on page 280 problem 6.
Supplementary None.

Core : Book problems: Section 9.1 on page 287 problems 2, 6, 7, 10.
Section 9.2 on page 294 problems 1, 2, 3, 5.
Supplementary:
- Draw the following graph.
  V={v1, v2, v3, v4, v5}
  E={v4v2, v1v3, v5v2, v5v3, v4v1}.
- Give an example of a proper graph on four vertices that is
  - complete and planar,
  - a tree (no loops nor isolated vertices),
  - not complete with no loops (aka cycles),
  - has exactly two edges and is planar,
  - contains a (proper) loop.
  For each graph, include the definition of the graph as a set of vertices and a set of edges and provide a model for the graph.
- How many graphs are there on four vertices? Prove your answer.

Core : Book problems: Section 9.2 on page 295 problems 14, 15a, 15b, 18a, 18d, 18e, 20b, 22b, 23a, 29.
Section 9.3 on page 299 problems 1, 3, 4a, 4b, 4c.
Also this problem :
Recall that a pseudograph is a weaker notion of graph were multiple edges and loops at a vertex are allowed.
We can define an isomorphism of pseudographs in the same way that we defined for graphs. Namely, an isomorphism is a map
on the vertex set which is a bijection and is edge preserving. What are the isomorphism classes of a pseudograph on
one vertex? on two vertices? In a pseudograph on n vertices, what degree sequences are possible?
Supplementary: Let G denote the graph whose vertex set consists of all 2-element subsets
of {1,2,3,4,5}, two of which are joined by an edge if and only if they are
disjoint. For example, ({1,2},{3,4}) is an edge in G but ({1,2},{2,3}) is
not an edge in G.
Prove that G is isomorphic to the graph depicted below by finding a
suitable labeling of the vertices in the drawing with the vertices of G.

Core : Book problems: Section 10.1 on page 309 problems 1, 3, 4bf, 11, 12, 13, 15, 16, 17, 18, 21, 23.
Also this problem :
Show that the book's definition of connectedness agrees with the definition given in class. That is, show that the two definitions below are logically equivalent.
Definition 1 (from class): A graph G=(V,E) is disconnected if there exist non-empty subgraphs H₁=(V₁,E₁) and H₂=(V₂,E₂) such that V₁ and V₂
partition V and E₁ and E₂ partition E. A graph is connected if it is not disconnected.
Definition 2 (from book): A graph G is connected if for any two vertices v,w there is a walk between v and w.
Supplementary: TBD.