Hosted by The Math Forum

Problem of the Week 1241

Petersen Graph with Small Labels

_____________________________________________
MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW
_____________________________________________

Show how to label the vertices of the Petersen graph with positive integers so that

  1. a graph edge exists if and only if the labels of the two ends of the edge have a common divisor greater than 1, and
  2. the sum of the 10 labels is under 100,000.

An interesting problem is to get this sum to be as small as possible.

The Petersen graph has 10 vertices and 15 edges; you can see it at MathWorld.

Source: Bernardo Recamán and Freddy Barrera, Colombia Aprendiendo, Bogotá, Colombia.

[View the solution]

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/


30 May 2017