Hamburger
EXPLORE
Documents Groups Templates Blog
ABOUT
Product Pricing About Authorea Careers
PRODUCT
EXPLORE
Documents Groups Templates Blog
ABOUT
About Us Careers
PRICING
Index
  1. In graph theory directed graphs
  2. Capture[1]
  3. The king chicken theorem is
  4. King chicken1
  5. The king chicken theorem also
  6. Div suggested exam problem from
  7. Graph
  8. References http ocw mit edu

King Chicken Theorem

In graph theory, directed graphs can be used to understand tournaments and theorems such as the king chicken theorem. First to understand the king chicken theorem, we will go over some terminology. A tournament is a directed graph that contains edges that have specific orientation. Tournament graphs are also used to show relationships between players and who beat who in a tournament. Complete graphs most often show this by using arrows. Any edge that points from \(i\) to \(j\) has directed orientation.  
In the graph above we can see that \(C_1\rightarrow C_2\) and can be read as \(C_1\) defeated \(C_2\). 
The king chicken theorem is explained by having a tournament where \(x\) is known as a king if \(x\) can walk to every vertex in no more than two steps. The theorem also holds that every tournament has \(\ge1\) king chicken. This theorem was first introduced by Professor Steve Maurer who taught at Swarthmore College. 
In the image above vertex \(1,2\) and \(3\) are kings because they can each get to every other vertex in at most \(2\) steps. Lets take a look at vertex \(1\), \(1\rightarrow3\), \(1\rightarrow3\rightarrow2\), and \(1\rightarrow3\rightarrow4\). The reason why vertex \(4\) is not a king is because it would take more than \(2\) steps to reach vertex \(2\).