Graph Theory Il Bipartite graphs are both useful and common. For example, every path, every tree, and every even-length cycle is bipartite. In turns out, in fact, that every graph not containing an odd cycle is bipartite and vice verse Theorem 2. A graph is bipartite if and only if it contains no odd cycle 2 The King chicken Theorem There are n chickens in a farmyard. For each pair of distinct chickens, either the first pecks the second or the second pecks the first, but not both. We say that chicken u virtually pecks chicken v if either Chicken u pecks chicken u Chicken u pecks some other chicken w who in turn pecks chicken u a chicken that virtually pecks every other chicken is called a king chicken We can model this situation with a tournament digraph. The vertices are chickens, and an edge u- v indicates that chicken u pecks chicken u. In the tournament be elow. three of the four chickens are kings Now were going to prove a theorem about chicken tournaments. The result is not very useful, but the proof involves both induction and digraphs, two of the most common mathematical tools in computer science Theorem 3(King Chicken Theorem). Every n-chicken tournament has a king, where n 1 Proof. The proof is by induction on n, the number of chickens in the tournament. Let P(n) be the proposition that in every n-chicken tournament, there is at least one king irst, we prove P(1). In this case, we can safely say that the lone chicken virtually pecks every other chicken, since there are no others. Therefore, the only chicken in the tournament is a king, and so P(1)is true Next, we must show that P(n)implies P(n+ 1)whenever n >1. Suppose there is a chicken tournament with chickens v1,..., Un+1. If we ignore the last chicken for the 'But if a chicken is a king, isn t it male? And if it is male, isn t it a rooster? Oh wellGraph Theory II 3 Bipartite graphs are both useful and common. For example, every path, every tree, and every even­length cycle is bipartite. In turns out, in fact, that every graph not containing an odd cycle is bipartite and vice verse. Theorem 2. A graph is bipartite if and only if it contains no odd cycle. 2 The King Chicken Theorem There are n chickens in a farmyard. For each pair of distinct chickens, either the first pecks the second or the second pecks the first, but not both. We say that chicken u virtually pecks chicken v if either: • Chicken u pecks chicken v. • Chicken u pecks some other chicken w who in turn pecks chicken v. A chicken that virtually pecks every other chicken is called a king chicken1. We can model this situation with a tournament digraph. The vertices are chickens, and an edge u v → indicates that chicken u pecks chicken v. In the tournament below, three of the four chickens are kings. king not a king king king Now we’re going to prove a theorem about chicken tournaments. The result is not very useful, but the proof involves both induction and digraphs, two of the most common mathematical tools in computer science. Theorem 3 (King Chicken Theorem). Every n­chicken tournament has a king, where n ≥ 1. Proof. The proof is by induction on n, the number of chickens in the tournament. Let P(n) be the proposition that in every n­chicken tournament, there is at least one king. First, we prove P(1). In this case, we can safely say that the lone chicken virtually pecks every other chicken, since there are no others. Therefore, the only chicken in the tournament is a king, and so P(1) is true. Next, we must show that P(n) implies P(n + 1) whenever n ≥ 1. Suppose there is a chicken tournament with chickens v1, . . . , vn+1. If we ignore the last chicken for the 1But if a chicken is a king, isn’t it male? And if it is male, isn’t it a rooster? Oh well