Prove that the petersen graph is not planar

Assignment Help Mathematics
Reference no: EM131585723

Question: 1. Prove that for a planar graph with k components, |V(G)|-|E(G)|+|F(G)| = 1+k.

2. Prove that the Petersen graph (shown in Figure) is not planar.

532_26.jpg

3. Show that if every face of a planar graph has four edges, then |E(G)| = 2|V(G)| -4.

4. For which n is Kn planar and for which n is Kn non planar? Make and prove a conjecture.

Reference no: EM131585723

Questions Cloud

Shares sell at the expected price : How much will the company receive if all shares sell at the expected price?
Information about various diseases : Go to the National Guideline Clearinghouse Website found at: guidelines.gov to locate information about various diseases.
Opportunities for marketers and consumers : Co-branding can be highly creative and may offer extraordinary opportunities for marketers and consumers alike.
What did you find most interesting about chapter : What did you find most interesting or "surprising" about chapter 3?
Prove that the petersen graph is not planar : Prove that for a planar graph with k components, |V(G)|-|E(G)|+|F(G)| = 1+k.
Element of team building : This is one element of team building that can be beneficial and allow individuals to get to know each other.
Conscious or unconscious tendency : One potential negative to teamwork is social loafing. Social loafing is "the conscious or unconscious tendency by some team members to shirk responsibilities.
Result in greater productivity or effectiveness : How might the advantages be leveraged to result in greater productivity or effectiveness? How might the disadvantages be overcome?
Why the given constraint is a weaker constraint : Theorem requires that G have no 3-cycles. This requirement could be replaced with the constraint that G be drawn with no faces of size 3.

Reviews

Write a Review

Mathematics Questions & Answers

  What ids the length of the longer side of the slab

the perimeter of a rectangular concrete slab is 94 feet and its area is 462 square feet. What ids the length of the longer side of the slab.

  Determine the sample size

Suppose you want to collect a sample of certain size from a continuous population to satisfy given confidence level and margin of error. What formula do you use to determine the sample size if you know the population proportion?

  How much will it drop by the time it reaches the catcher

A major league pitcher can throw a baseball in excess of 48.8 m/s. if a ball is thrown horizontally at this speed, how much will it drop by the time it reaches the catcher who is 15.7 m away from the point of release?

  At what rate did she spend her money

Nata spent $28 on 2 DVDS. At this rate,how much would 5 DVDS cost? At what rate did she spend her money

  Discuss sample of three transistors

QUALITY CONTROL A sample of three transistors taken from a local electronics store was examined to determine whether the transistors were defective.

  How large a sample of visitors should be selected

Investors at a theme park would like to estimate the unknown proportion (p) of visitors who have visited the theme park in the past five years. They would like to be 90% confident of achieving an accuracy of at least 0.04. How large a sample of vi..

  Find the open intervals on which the function is increasing

Find the critical numbers of f. Find the open intervals on which the function is increasing or decreasing. Apply the First Derivative Test to identify the relative extremum.

  What is the temperature of the coffee

A cup of coffee at 179 degrees is poured into a mug and left in a room at 66 degrees. After 7 minutes, the coffee is 133 degrees. Assume that the differential equation describing Newton's Law of Cooling is (in this case)dT/dt=k(T-66).What is the t..

  What is the probability that the oilfield will be purchased

what is the probability that the oilfield will be purchased by Exxon?

  Determine how many udges the city needs

To avoid creating a backlog, all cases must be handled by the end of December. Formulate a linear program that can be used to determine how many udges the city needs.

  Find the speed of the plane in still air

plane can travel 490 miles per hour with wind and 410 miles per hour against the wind, find the speed of the plane in still air.

  Utilization factor for the system

1. In regression equations represented by Y = 2 + 3X, if value X =2 then predicted value of Y is 10. 2. Residual = Actual Value - Predicted Value 3. In a queuing system, percentage of time a server is busy is called the utilization factor for the ..

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd