Graph Theory Il Let m be the number of faces that meet at each corner of a polyhedron, and let n be the number of sides on each face. In the corresponding planar graph, there are m edge incident to each of the u vertices Since each edge is incident to two vertices we know: mu= 2e Also, each face is bounded by n edges. Since each edge is on the boundary of two faces, we have Solving for v and f in these equations and then substituting into Euler's formula gives m The last equation places strong restrictions on the structure of a polyhedron. Every non- degenerate polygon has at least 3 sides, so n > 3. And at least 3 polygons must meet to from a corner, so m >3. On the other hand, if either n or m were 6 or more then the left side of the equation could be at most 3+6=2, which is less than the right side. Checking the finitely-many cases that remain turns up five solutions. For each valid combination of n and m, we can compute the associated number of vertices u, edges e, and faces f. And polyhedra with these properties do actually exist hedron 334 6 4 tetrahedry 438126 cube 346 128 octahedron 35123020 5 20 30 12 dodecahedron The last polyhedron in this list, the dodecahedron, was the other great mathematical se cret of the Pythagorean sect 4 Halls Marriage Theorem a class contains some girls and some boys. Each girl likes some boys and does not like others. Under what conditions can each girl be paired up with a boy that she likes? We can model the situation with a bipartite graph. Create a vertex on the left for each girl and a vertex on the right for each boy. If a girl likes a boy, put an edge between them or example, we might obtain the following graphGraph Theory II 9 Let m be the number of faces that meet at each corner of a polyhedron, and let n be the number of sides on each face. In the corresponding planar graph, there are m edges incident to each of the v vertices. Since each edge is incident to two vertices, we know: mv = 2e Also, each face is bounded by n edges. Since each edge is on the boundary of two faces, we have: nf = 2e Solving for v and f in these equations and then substituting into Euler’s formula gives: 2e 2e = 2 m − e + n 1 1 1 1 + = + 1 m n e 2 1 The last equation places strong restrictions on the structure of a polyhedron. Every non­ 1 degenerate polygon has at least 3 sides, so n ≥ 3. And at least 3 polygons must meet to from a corner, so m ≥ 3. On the other hand, if either n or m were 6 or more, then the left side of the equation could be at most + = , which is less than the right side. Checking 3 26 the finitely­many cases that remain turns up five solutions. For each valid combination of n and m, we can compute the associated number of vertices v, edges e, and faces f. And polyhedra with these properties do actually exist: n m v e f polyhedron 3 3 4 6 4 tetrahedron 4 3 8 12 6 cube 3 4 6 12 8 octahedron 3 5 12 30 20 icosahedron 5 3 20 30 12 dodecahedron The last polyhedron in this list, the dodecahedron, was the other great mathematical se￾cret of the Pythagorean sect! 4 Hall’s Marriage Theorem A class contains some girls and some boys. Each girl likes some boys and does not like others. Under what conditions can each girl be paired up with a boy that she likes? We can model the situation with a bipartite graph. Create a vertex on the left for each girl and a vertex on the right for each boy. If a girl likes a boy, put an edge between them. For example, we might obtain the following graph: