(a) Let k Z+, k ¥ 3. If G = (V, E) is a connected planar graph...

Question:

(a) Let k ˆˆ Z+, k ‰¥ 3. If G = (V, E) is a connected planar graph with |V| = v, |E| = e, and each cycle of length at least k, prove that

(b) What is the minimal cycle length in K3,3?
(c) Use parts (a) and (b) to conclude that K3, 3 is nonplanar.
(d) Use part (a) to prove that the Petersen graph is nonplanar.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For book-img-for-question

Discrete and Combinatorial Mathematics An Applied Introduction

ISBN: 978-0201726343

5th edition

Authors: Ralph P. Grimaldi

See More Books

Question Posted: Jun 21, 2016 08:48 AM

See More Questions

Let k denote the number of successes observed in a sequence of n independent Bernoulli trials, where p = P(success). (a) Show that the critical region of the likelihood ratio test of H 0 : p = 1/2...
Consider the measurable space (W, A) and let A n A, n = 1, 2, then recall that And (i) Show that A n A n . (If also A n A n so that A n = n A n then this set is denoted by A n and is called the...
Let W be an abstract set, and let C be an arbitrary nonempty class of subsets of W. Define the class F 1 to consists of all members of C as well as all of their complements; i.e., F 1 = {A W; A C...
Measure each amount given in Problems 1721. a. Container C in ounces b. Container C in milliliters mL 500- 400- 300 200- 100 cups 2 1 -16-ez -14 oz -12 oz -110 oz 8 oz -16 oz -4 oz 2 oz Container C...
When should interviewers probe? Give some examples of how probing should be done.
Multiple Choice Questions 1. Halifax Corporation has a December 31 fiscal year-end. As of December 31, Year 1, the company has a debt covenant violation that results in a 10-year note payable to Nova...
1. Find the z-score that corresponds to a cumulative area of 0.3632. 2. Find the z-score that has 10.75% of the distributions area to its right.
The following questions illustrate nonannual compounding. a) One hundred dollars is placed in an account that pays 12 percent. How much will be in the account after one year if interest is compounded...
Sharkers Company supplied you with the following information: Share Dividend expected next year (R) Dividend Growth Rate (%) Required Return (%) A 1.10 9 12 B 3.80 6 11 C 0.80 13 17 D 2.60 12 16 E...
For the system shown in Fig. 8.17, compute the power delivered by the pump to the water to pump 50 gal/min of water at 60F to the tank. The air in the tank is at 40 psig. Consider the friction loss...
(a) Let G = (V,E) be a loop-free connected graph with | V | 11. Prove that either G or its complement must be nonplanar. (b) The result in part (a) is actually true for | V | 9, but the proof for |...
(a) Find a dual graph for each of the two planar graphs and the one planar multi graph in Fig. 11.72. (b) Does the dual for the multigraph in part (c) have any pendant vertices? If not, does this...
In the bivariate meta-analysis of data on true positives and negative $\mathrm{CT}$ scan diagnoses, adopt a scale mixture of normals for the $\theta_{i}=\left(\theta_{i 1}, \theta_{i 2} ight)$ in...
As expected, the Federal Reserve announced it would hold its key interest rate steady in the range of 1.001.25 percent. But the Feds remark that inflation is expected to stay somewhat below 2 percent...
What type of inflation process does John Cochrane warn could happen? Explain the role that inflation expectations would play if the outbreak of inflation were to happen with little warning. Economist...
On January 1, 2017, Terrys Towing Service owned 4 tow trucks valued at $300,000. During 2017, Terrys bought 2 new trucks for a total of $180,000. At the end of 2017, the market value of all of the...
The 2016 inflation control target agreement between the Government of Canada and the Bank of Canada runs to the end of 2021. a. What does the inflation control agreement say about the Banks control...
Explain how the tariff on textiles will change the price that Canadians pay for textiles, the quantity of textiles imported, and the quantity of textiles produced in Canada. Suppose that in response...
In Exercises (a) draw the graph of the function. Then find its (b) domain and (c) range. (x) = 2|x + 4| - 3
Cornell and Roberts are partners who agree to admit Stanley to their partnership. Cornell has a capital balance of $80,000 and Roberts has a capital balance of $120,000. Cornell and Roberts share net...
Show that sin jx is orthogonal to sin kx in [- n, n] for j k, j, k 1.
Show that ||1||2 = 2 and |cos kx||2 = in [- , ]
In Exercises 1 and 2, find the third-order Fourier approximation to f on [- , ]. 1. f(x) = |x| 2. f(x) = x2
Question: Part One: Memo Write an analysis of the impact of tax laws and incentives as demonstrated in this current years tax return. Specifically, you must address the following: Explain the...
From the following ledger balances, prepare a trial balance for the Cheyenne Corp. at June 3 0 , 2 0 2 2 . All account balances are normal.Accounts Payable $ 1 0 , 0 0 0 , Cash $ 7 , 4 0 0 , Common...
Kathy is mixing fruit punch in a 32-cup punch bowl for a party. She plans to add at least 20 cups of fruit juice to the bowl before adding ginger ale. Identify the graph that represents the amounts...

(a) Let k Z+, k ¥ 3. If G = (V, E) is a connected planar graph...

Question:

k-2

Step by Step Answer:

a 2e kr k2 e v 2 ke k2 v e kk2v2 b 4 c In K 33 e 9 ...View the full answer

Discrete and Combinatorial Mathematics An Applied Introduction

Students also viewed these Linear Algebra questions