Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

i have searched through internet, but found only paid articles. Need to understand how Petersen graph can be contracted to K33, it says what through deleting the central vertex of 3-symmetric drawig. But what is 3-symmetric drawing?

share|improve this question
    
They mean a drawing with 3-fold symmetry. The most usual drawing has 5-fold symmetry, but you should be able to track down other drawings. –  Will Orrick May 7 '13 at 16:49

2 Answers 2

up vote 1 down vote accepted

Here's a drawing of the Petersen graph with three-fold symmetry. With the aid of the drawing, you should be able to find the needed contraction. Petersen graph with three-fold symmetry

It is interesting that the method suggested in your hint, which requires the deletion of a vertex and its three incident edges followed by three contractions, is not the only way to find a $K_{3,3}$ minor in the Petersen graph. An alternative requires no vertex deletions and only two edge deletions. If the graph is drawn in the usual way with five-fold symmetry, then the two deleted edges should be parallel to each other. Four contractions will then be needed.

share|improve this answer
    
Your picture are very well done, could you say me which graphics editor you used? Thanks. –  Yola May 8 '13 at 7:28
1  
@Yola : I made the graph in Mathematica. I had to compute the vertex coordinates explicitly. –  Will Orrick May 8 '13 at 8:58

Perhaps this should help. Here is a 3-coloring of the Petersen graph. Now contract so independent sets stay independent...

http://en.wikipedia.org/wiki/File:Petersen_graph_3-coloring.svg

In more detail, contract all blue to the neighboring green, and a pair of reds to get 3 reds and 3 greens...

share|improve this answer
    
The red vertex connected to three blue vertices should be the center vertex in the diagram with three-fold symmetry. After contracting the blues to greens, don't you end up with $K_{4,3}$? I think you will then have to delete a red rather than contracting it with another red. –  Will Orrick May 8 '13 at 9:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.