1
$\begingroup$

Please help me prove Petersen graph is tripartite.

I know that is not bipartite by brute force, however I'm not sure how toextend this for Tripartite. I have a only clue that The chromatic number of the Petersen graph is 3 and it has 5 cycle.

Do we have any standard proof or do we have to assume things inorder to prove this. kindly advise.

$\endgroup$
  • 1
    $\begingroup$ Well, since you need to prove that it's tripartite, giving a tripartition (or a 3-coloration) is enough. $\endgroup$ – H. Potter Feb 29 '16 at 7:26
  • $\begingroup$ Thank you. Would you be so kind to eloborate the above. $\endgroup$ – Allan Feb 29 '16 at 7:29
  • 2
    $\begingroup$ It would be better if you can solve it by yourself. Just draw Petersen graph on a paper and try to color its vertices. $\endgroup$ – H. Potter Feb 29 '16 at 7:30
  • $\begingroup$ What is your definition of the Petersen graph? $\endgroup$ – bof Feb 29 '16 at 7:49
  • $\begingroup$ Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a cubic symmetric graph and is nonplanar. $\endgroup$ – Allan Feb 29 '16 at 7:58
1
$\begingroup$

The Petersen graph can be defined as the graph whose vertices are the two-element subsets of $\{1,2,3,4,5\},$ with two vertices being adjacent if they are disjoint sets.

The Petersen graph is not $2$-colorable (bipartite) because it contains a $5$-cycle, e.g., the cycle $$\{1,2\},\{3,4\},\{5,1\},\{2,3\},\{4,5\},\{1,2\}.$$

We can show that the Petersen graph is $3$-colorable (tripartite) by exhibiting a proper $3$-coloring of the vertices:

Color a vertex red if its least element is $1$; i.e., the red vertices are $$\{1,2\},\{1,3\},\{1,4\},\{1,5\}.$$ Color a vertex white if its least element is $2$; i.e., the white vertices are $$\{2,3\},\{2,4\},\{2,5\}.$$ Color the remaining vertices blue; i.e., the blue vertices are $$\{3,4\},\{3,5\},\{4,5\}.$$

$\endgroup$
  • $\begingroup$ Thank you again. Accepted. $\endgroup$ – Allan Feb 29 '16 at 8:42
  • 1
    $\begingroup$ A Kneser graph, nice... $\endgroup$ – draks ... Feb 29 '16 at 11:26
2
$\begingroup$

Use "This drawing with order-3 symmetry"

enter image description here

(colors added to figure given here)

$\endgroup$
0
$\begingroup$

Since the chromatic number is three, i.e., vertices can be colored with three colors such that there is no edge between the same color vertices. Now consider a tri-partition of vertex set, where each partition consists of verices of same color.

$\endgroup$
  • $\begingroup$ can you please show me the color code of its vertices. Will that be sufficient for this proof? $\endgroup$ – Allan Feb 29 '16 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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