2602 Homework #8-#11

MATH 2602 Homework #8-#11
Due Wednesday Mar 11 - Apr 8, covering the material of Exam 3 on Apr 8

Core : Book problems: Section 9.1 on page 287 problems 2, 5, 6, 7, 10.
Section 9.2 on page 294 problems 1, 2, 3, 5, 6.
Also:
- 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.
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.

Core : Book problems: Section 10.2 on page 317 problems: 1, 3, 5.
Section 10.3 on page 324 problems: True and False problems 1-10, and problems 7, 8 on page 325.
Section 11.2 on page 350 problems: 1, 2.
Section 13.1 on page 417 problems: 1, 2.

Core : Book problems: Section 13.2 on page 425 problems: 4, 7, 8.
Section 13.1 on page 417 problems: 4, 5.
Section 12.2 on page 283 problems: 2, 8.