MAT118 Review for Midterm II

Material from Week 3

Understand how to construct Pascal's triangle (see notes). Understand the relation between the triangle and the coefficients in $(a+b)^n$ (Binomial Theorem, in notes). Be able to explain why the sum of the numbers in row $n$ is $2^n$, and their alternating sum is $0$.

Material from Week 4

Understand the "dominoes" solution to the Königsberg bridge problem (see page 389). Be able to determine by inspection if a graph admits an Euler circuit (no vertices of odd degree; Theorem on page 394), or if it admits an Euler path (two vertices of odd degree; Mindscape 21 on page 398). If a graph admits an Euler circuit, be able to describe the circuit by numbering the edges and listing them as they occur in the circuit. Same for an Euler path. See instructions on pages 392-393.

Material from Week 5

Understand that a connected planar graph must satisfy Euler's Theorem: $V-E+F=2$, where $V$ is the number of vertices, $E$ the number of edges, and $F$ the number of planar regions separated by the edges of the graph. Remember to count the outside as one of the regions (page 404).

Understand that if a planar graph has $C$ connected pieces, then it satisfies $V-E+F=C+1$ (Mindscapes 26, 27, 28 page 411).

Understand the correspondence between the vertices, edges and regions of a planar graph and the vertices, edges and faces of a graph drawn on a sphere (page 406). So these must satisfy $V-E+F=2$. Understand how all five regular polyhedra correspond to graphs on a sphere (see Mindscape 25 on page 411); know their names and be able to check that they satisfy $V-E+F=2$.

Understand how to draw the dual of a planar graph, or of one on a sphere: a dual-vertex inside each face; a dual-edge between dual-vertices if the corresponding faces share an edge (the dual-edge intersects this edge in one point and does not intersect any other edge); a dual-face corresponding to each vertex: its dual-edges correspond exactly to the edges issuing from that vertex. Understand that the dual of a peninsula edge (page 419) is a dual-edge loop based at the dual-vertex corresponding to the region the peninsula sticks into. And conversely the dual of a loop is a dual-edge peninsula with its tip at the dual-vertex corresponding to the region enclosed by the loop.

A planar graph and its dual.

Understand that with this construction the dual of a tetrahedron (4 vertices, 4 triangular faces, each vertex belongs to 3 edges) is again a tetrahedron. That the dual of a cube (8 vertices, 6 square faces, each vertex belongs to 3 edges) is an octahedron (6 vertices, 8 triangular faces, each vertex belongs to 4 edges). And that the dual of a dodecahedron (20 vertices, 12 pentagonal faces, each vertex belongs to 3 edges) is an icosahedron (12 vertices, 20 triangular faces, each vertex belongs to 5 edges). And vice-versa, since the dual of the dual gets back to the original graph. Duality for regular polyhedra is explained in section 4.5.

Material from Week 6

Understand that the (3 houses, 3 utilities) problem amounts to asking if there exists a planar graph with two sets of vertices $A, B, C$ and $X, Y, Z$, and edges $XA, XB, XC, YA, YB, YC, ZA, ZB, ZC$. "Planar" means in particular that one edge cannot intersect another. (Of course, they are allowed to meet at vertices). And asking if the pentagram (5 vertices, all 10 possible edges) can be drawn without edges intersecting is asking if there exists a planar graph with vertices $A, B, C, D, E$ and edges $AB, AC, AD, AE, BC, BD, BE, CD, CE, DE$. Be able to explain why, for a connected, planar graph with no loops and no multiple edges, the number $E$ of edges and the number $V$ of vertices must satisfy $E \leq 3V-6$ (page 419). This rules out the pentagram. Also understand that for a bipartite graph like the (3 houses, 3 utilities) the inequality becomes $E \leq 2V-4$ (page 420). This shows the 3 houses cannot be connected to the 3 utilities without one of the lines crossing. Use Mindscapes 1-16 on pages 428-30 for review.

March 12, 2013