Question

Bonus 1 A walk in a graph G is a sequence of vertices V1, V2, ..., Uk such that {Vi, Vi+1} is an edge of G. Informally, a walk is a sequence of vertices where each step is taken along an edge. Note that a walk may visit the same vertex more than once. A closed walk is a walk where the first and last vertex are equal, i.e. v1 = Uk. The length of a walk is the number of " steps" taken in the walk, i.e. k-1. Let G be a planar graph and with f faces and e edges. Say that a vertex and a face are "touching" if the dis- tance between the vertex and the face is 0. Note that whether or not a particular vertex touches a particular face depends on the way G is drawn. Let F, be a face of G. Define the degree of F, as the length of the shortest closed walk visiting every vertex which touches F. Show that deg(F1) + ... deg(F) = 2e Bonus 2 You bring a date to a dinner party consisting of 4 other couples. In total there are 5 couples at the party. During the course of the evening, some people shake hands. No one shakes their own hand or the hand of their date. No pair of people shake hands more than once. At the end you ask each of the 9 other guests how many hands they shook, and they each give a different answer. How many hands did your date shake?

Answer 1

G be a planar graph with f faces & e edges. claim: - Each edge contributes +2 in the sum of the degrees of faces. proof or Case-II If the edge is a non-spike edge, then it has too faced on each side of it. i.e. it contributes 2 in the degree hum [Care -2/ For a spike edge we have to trace back that edge to complet a closed walk. i.e. it also contributes 2 in the degree surn. Hence & deg (F) = 20 Spike edge e G Non-spike edge Hence