Hosted by The Math
Problem of the Week 956
Counting Nonadjacent Edges
Given a convex n-gon, with vertices denoted in order by P_1, P_2, ..., P_n, let G_n be the graph obtained as a result of tracing the zig-zag polygonal path from P_1 to P_(n-1) to P_2 to P_(n-2), etc. and eventually to P_m where
Note the edges and vertices of the original n-gon are included in G_n. For n >= 3 let a(n) be the number of sets of nonadjacent edges from G_n. For example if we start with a convex 4-gon which has four vertices and four edges, we add the edge connecting P_1 to P_3. This graph has a(4) = 8 since in addition to the empty set, G_4 has five sets consisting of a single edge each, and two sets consisting of two nonadjacent edges.
Source: Emeric Deutsch of Polytechnic University, Brooklyn, NY for MATHEMATICS MAGAZINE. This problem originally appeared in the February 2001 issue.© Copyright 2002 Stan Wagon. Reproduced with permission.