Chapter 14 Cardinality Rules606
A set of two edges that share a vertex is called anincident pair(i.p.); the shared
vertex is called thecenterof the i.p. That is, an i.p. is a set,
fhu—vi;hv—wig;whereu;vandware distinct vertices, and its center isv.
(a)How many triangles are there?
0.5in(b)How many incident pairs are there? 0.5in
Now suppose that every edge inGis colored either red or blue. A triangle or i.p.
is calledmulticoloredwhen its edges are not all the same color.
(c)Map the i.p.
fhu—vi;hv—wigto the triangle
fhu—vi;hv—wi;hu—wig:
Notice that multicolored i.p.’s map to multicolored triangles. Explain why this
mapping is 2-to-1 on these multicolored objects.
(d)If two people are not friends, they are calledstrangers. If every pair of people
in a group are friends, or if every pair are strangers, the group is calleduniform.
The final part of this problem will show that
There are at most 36 multicolored i.p.’s.Explain why this fact and the results of parts (a) and (c) imply that
Every set of six people includestwouniform three-person groups.(e)Show that at most six multicolored i.p.’s can have the same center. Conclude
that there are at most 36 possible multicolored i.p.’s.
Hint:A vertex incident torred edges andbblue edges is the center ofrbdifferent
multicolored i.p.’s.
Exam Problems
Problem 14.32.
There is a robot that steps between integer positions in 3-dimensional space. Each
step of the robot increments one coordinate and leaves the other two unchanged.
(a)How many paths can the robot follow going from the origin.0;0;0/to.3;4;5/?(b)How many paths can the robot follow going from the origin.i;j;k/to.m;n;p/?