Advanced High-School Mathematics

SECTION 2.2 Elementary Graph Theory 131 Use Prim’s algorithm to find a minimal spanning tree in the graph below: Use the method ...

132 CHAPTER 2 Discrete Mathematics Of course, a weighted graph can be thought of as being directed where the weights are the sam ...

SECTION 2.2 Elementary Graph Theory 133 Step 1. Find the vertices v in G such that (v 0 ,v) is a directed edge. Temporarily mark ...

134 CHAPTER 2 Discrete Mathematics Step 5. Find all new vertices connected to v 2 ; mark these with their distances from v 0 (al ...

SECTION 2.2 Elementary Graph Theory 135 such that{f(v 1 ),f(w 1 )}is an edge of G 2 exactly when{v 1 ,w 1 } is an edge ofG 1. In ...

136 CHAPTER 2 Discrete Mathematics The next important family involves the so-called bipartite graphs. The simple graph G is call ...

SECTION 2.2 Elementary Graph Theory 137 There are two fundamental theorems which give criteria for a graph to be planar. They’re ...

138 CHAPTER 2 Discrete Mathematics The next planarity condition is somewhat more useful but slightly more technical. First of al ...

SECTION 2.2 Elementary Graph Theory 139 Euler’s formula and consequences Once a planar graph has been drawn in the plane, it not ...

140 CHAPTER 2 Discrete Mathematics is 2: Theorem. (Euler’s Formula)If M be a connected planar map, then χ(M) = 2. Proof. Let T b ...

SECTION 2.2 Elementary Graph Theory 141 From which it follows that e′ ≤ 3 v′− 6. However, e′ = e−k and v′=v−k for some fixed non ...

142 CHAPTER 2 Discrete Mathematics Here’s a slightly more sophisticated problem. Define the graphsG 1 andG 2 , as follows. Star ...

SECTION 2.2 Elementary Graph Theory 143 Prove that any cycle in a bipartite graph must have even length. Conversely, if every c ...

144 CHAPTER 2 Discrete Mathematics (a) Show thatT∗is a spanning tree inG∗. (b) Conclude that v =eT+ 1 and f =eT∗+ 1, where eT is ...

Chapter 3 Inequalities and Constrained Extrema 3.1 A Representative Example The thrust of this chapter can probably be summarize ...

146 CHAPTER 3 Inequalities -4 -2 2 4 -4 -2 2 4 x +y =4 2xy=c>0 xx 2 2 x y 2xy=c< 0 Problem. Given that x^2 +y^2 = 4, find ...

SECTION 3.2 Classical Inequalities 147 -4 -2 2 4 -4 -2 2 4 x +y =c xy=2 xx 22 x As a final variation on the above y theme, note ...

148 CHAPTER 3 Inequalities Harmonic Mean: HM(x 1 ,x 2 ,...,xn) = n 1 x 1 + 1 x 2 +···+ 1 xn ; Quadratic Mean:^2 QM(x 1 ,x 2 ,... ...

SECTION 3.2 Classical Inequalities 149 since we have already shown that GM(x,y)≤ AM(x,y) forx, y≥ 0, we now have HM(x 1 ,x 2 ) = ...

150 CHAPTER 3 Inequalities then we see that AM(x 1 ,...,xn)≤QM(x 1 ,...,xn) is true without the assumption that allxi are positi ...