Three-Channel Assignment on a Coupled Interference Graph
A regional wireless board must assign one of three channels to each of six transmitters A, B, C, D, E, F. Interference occurs along the links AB, BC, CD, DE, EF, FA, plus the additional links AC and DF. Channels are labeled 1, 2, and 3, and adjacent transmitters must receive different channels. The board first wants to know whether three channels suffice at all. It then wants the exact number of valid channel assignments using all three labels available, counting assignments that differ on any transmitter as different. A vendor claims that because the graph contains two triangles, the count is simply 3!·3! =36: color each triangle independently. A board member suspects that the two linking edges CD and FA impose extra restrictions. The board needs a chromatic-number judgment, an exact count, and a check on the vendor's independence claim.
1. Determine the chromatic number of the interference graph. Exhibit a 3-coloring and explain why 2 colors cannot suffice.
Read the worked answer
The triangle A-B-C requires three distinct colors, so χ≥3. A 3-coloring exists: A=1, B=2, C=3, D=1, E=2, F=3. Check edges: AB=1/2, BC=2/3, AC=1/3, CD=3/1, DE=1/2, EF=2/3, DF=1/3, FA=3/1 all differ. Thus χ=3. Two colors cannot suffice because the triangle A-B-C alone would need three colors.
2. Count the number of proper 3-colorings with labeled colors 1,2,3. Show the case analysis.
Read the worked answer
Count by first coloring triangle ABC. A has 3 choices, B has 2 choices, and C must be the third color, so 6 choices. By symmetry fix A=1, B=2, C=3. Since D is adjacent to C=3, D∈{1,2}. Case D=1: E is adjacent to D, so E∈{2,3}. If E=2, then F must avoid D=1, E=2, A=1, so F=3. If E=3, then F must avoid 1 and 3, so F=2. That gives 2 assignments. Case D=2: E∈{1,3}. If E=1, F must avoid D=2, E=1, A=1, so F=3. If E=3, F must avoid 2,3,1, which is impossible. That gives 1 assignment. Total per fixed ABC is 3, so total valid assignments =6·3=18.
3. Evaluate the vendor's claim that the count is 36. Where does independence fail?
Read the worked answer
The vendor's 36 comes from coloring each triangle independently: 6 ways for ABC and 6 for DEF. That would be correct only if no edge joined the two triangles. But edges C-D and F-A couple the choices: D cannot use C's color and F cannot use A's color. The case analysis shows that for each fixed coloring of ABC, only 3 of the 6 colorings of DEF are valid, not 6. Hence 6·3=18, not 36.