Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an $n$-sided polygon, how many ways can you color the vertices using $k$ colors so that no two adjacent vertices have the same color?

(Inspired by 2011 AMC 12 A #16 – I'm able to do this for small cases but not in general.)

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

Here are two ways to do the problem, both of which use graph theory. The problem is equivalent to counting the number of closed walks of length $n$ on the complete graph $K_k$ on $k$ vertices. The number of closed walks of length $n$ on a graph $G$ with adjacency matrix $A$ is given by $\text{tr } A^n = \sum_{i=1}^k \lambda_i^n$ where $\lambda_i$ are the eigenvalues of $A$.

So it suffices to compute the eigenvalues of the adjacency matrix of $K_k$. This is a nice exercise, but for the sake of completeness I will tell you that they are $k-1, -1, -1, ...$. So the final answer is

$$(k-1)^n + (k-1)(-1)^n.$$


The second method is to observe that the problem is equivalent to computing the chromatic polynomial of the cyclic graph $C_n$. This can be done by induction and the deletion-contraction recurrence, and you get the same answer.


Note that these two solutions generalize in different directions. The first solution suggests a generalization of the problem where you replace $K_k$ with a more complicated graph, whereas the second solution suggests a generalization of the problem where you replace $C_n$ with a more complicated graph. Both problems are in turn special cases of the following problem.

Definition: Let $G, H$ be two (undirected, simple) graphs. A morphism $f : G \to H$ is a function $f : V_G \to V_H$ sending vertices of $G$ to vertices of $H$ such that, if $u, v \in G$ are connected by an edge, then $f(u), f(v)$ are also connected by an edge.

Problem: How many morphisms are there from a given graph $G$ to a given graph $H$?

The walk problem corresponds to letting $G = C_n$ and letting $H$ be arbitrary, while the coloring problem corresponds to letting $H = K_k$ and letting $G$ be arbitrary. Both of these are very special cases. The general problem is interesting; I have no idea what's known about it.

share|improve this answer
    
Perfect, exactly what I was looking for! –  Ben Alpert Feb 13 '11 at 1:17
add comment

Do you know about the chromatic polynomial? That has a simple skein formula which can be easily calculated for n-gons. It is a polynomial in k, the number of possible colorings.

share|improve this answer
    
Thanks; I'm accepting Qiaochu's answer because it's more complete (and also was a few seconds before yours). –  Ben Alpert Feb 13 '11 at 1:16
    
Yes Qiaochu beat me to it! –  Grumpy Parsnip Feb 13 '11 at 2:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.