Cycle graph with n vertices and n edges

Reference no: EM13937675

1. Let Cn be the cycle graph with n vertices and n edges and let Pn(x) be its chromatic polynomial.

(a) Explain why P3(x) = x (x - 1) (x - 2) .

b) If n > 3 , describe the two graphs that are obtained when one ‘cuts Cn open along an edge' and then ‘stitches it back up.'

(d) Hence prove by Induction that Pn(x) = (x - 1)n + (-1)n(x - 1) for all n ≥ 3 . (e) In how many ways can the cycle graph with 11 vertices be coloured using 10 colours?

2. Let Wn (W for wheel) be the graph obtained by joining all of the vertices on the ‘rim' Cn (a cycle graph with n vertices) with edges (‘spokes') to a central vertex, so W3 is the complete graph on 4 vertices (shown at left below) and W4 is the graph in the middle below

Reference no: EM13937675

Questions Cloud

Competing design agency as part of growth strategy : Wombat+Wombat is a well-established creative design agency located on the East Coast. It has experienced very stable growth in both earnings and dividends over the past 10 years, averaging 7% per annum. Wombat+Wombat is considering the acquisition of..

Write a c++ program to read from a file and sort it : Using this information the program should request a user entered account number and display the corresponding name and account balance.

Bowlby theory of attachment and impairment of attachment : First become familiar with Bowlby's theory of attachment and impairment of attachment. Then share what you think your parental attachment was when you were young

Is frogs leap a socially responsible business : a) Is Frog's Leap a socially responsible business? b) How does it stack up against its wine industry peers?

Cycle graph with n vertices and n edges : Let Wn (W for wheel) be the graph obtained by joining all of the vertices on the ‘rim' Cn (a cycle graph with n vertices) with edges (‘spokes') to a central vertex, so W3 is the complete graph on 4 vertices (shown at left below) and W4 is the grap..

Risks will affect risk premium that investors will demand : Which of the following risks of a stock are likely to be firm-specific, diversifiable risks, and which are likely to be systematic risks? Which risks will affect the risk premium that investors will demand?

Depth study of a literary text for the period : You are a Primary (Prep/Foundation-Year 6/7) school teacher* with a class of 25 students with varying ability levels. Your school has introduced an English literacy block to meet the systemic requirements for 7.5 hours of English per week - one an..

Trading at premium or discount relative to the spot rate : Assume that interest rate parity holds and that 90-day risk-free securities yield 5% in the United States and 5.3% in Germany. In the spot market, 1 euro equals $1.40. What is the 90-day forward rate? Is the 90-day forward rate trading at a premium o..

Walk the appalachian trail unless : Write the following propositions in the form p → q for appropriate p and q. (a) Willy gets caught whenever he cheats. (b) A necessary condition for Jim to buy a computer is that he obtains $2,000. (c) The website will be accessible only if you hav..

User Account

All Pages