8. Fill in the part of the proof of Theorem 1.12 that the textbook and Iskimmed

Question

8. Fill in the part of the proof of Theorem 1.12 that the textbook and Iskimmed over: Look at "Assume, to the contrary, that there exist two adjacent vertices in U or two adjacent vertices in W. Since these two situations are similar, we will assume that there are vertices v and w in W such that vw E E(G) What happens in the other case that is, what happens if there exist two adjacent vertices in U? 9. Recall that we can form an oriented graph by taking a graph and assigning directions (orientations) to cach edge, turning each into an arc. How many possible oriented graphs can be formed from a labelled copy of Cu? 10. Consider Group l of the 2016 ICC World Twenty20 competition in cricket (see list of results at https://en.wikipedia.org/viki/2016-ICC-World Tventy20nGroup.1; if that does not work, try http://tinyurl.com/Math428HW3Link1). Draw the tournament ponding to this tournament

Explanation / Answer

Let U is consist of all vertices of G whose distance from u is even

To prove by contradiction

If there exist two adjaccent vertices in U

Let v & w are two adjaccent vertices in U

therefore d(u,v) & d(u,w) are even

d(u,v)=2s aand d(u,ww)=2t

where s,t are non negative integer

Let p'=(u=v0,v1-----v2s=v) be u-v geodesic

P"=(u=w0,w1--------w2t) be u-w geodesic

Let x is least vertex

in any case x=vi   for some integer i>=0

d(u,vi)=i

since x in on P" & wi is the only vertex of P" whose distance from u is i

therfore x=vi=wi

than

C=(vi,vi+2,----v2s,w2t,w2t+2,-----wi=vi)

is cycle of length

[(2s-i)+(2t-i)]+1=2s+2t-2i+1

=2(s+t-i)+1

so C is odd cycle

which ih contadiction to G not cantain odd cycle

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.