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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In my project to construct the outer automorphism group for $S_6$ I have come across a need (or desire) to visualize a graph that has 15 vertices, with each vertex having 6 incident edges and 3 incident "triangles." (By my count, that makes 15 total vertices, 45 total edges, and 15 total triangles.) No matter how I try to draw this, I am not successful. I started with a regular 15-sided figure, but this lead nowhere quickly, and I can see clearly that if this graph even exists, it will have to be a concave/self-intersecting polygon, geometrically. Am I barking up the wrong tree, or is there a way to realize this graph?

Edit: In case anybody is wondering, the reason I am interested in this graph is because I am considering all the two-cycles in $S_6$ as "vertices," for which there are $6 \choose 2$ aka 15 total vertices; two vertices are joined by an edge if they commute, ie, if they are disjoint. Three vertices form a "triangle" if they are pairwise disjoint.

share|cite|improve this question
Label the vertices by the 15 ordered pairs of elements of the set $\{1,2,3,4,5,6\}$ and join two vertices if their corresponding ordered pairs have empty intersection. – Derek Holt Oct 21 '12 at 16:49
@DerekHolt, that's exactly how I came up with the construction for the graph! But forgive me if I am being stupid, but I still don't see how that helps me draw the graph – tacos_tacos_tacos Oct 21 '12 at 16:52
up vote 2 down vote accepted

Start with $15$ disjoint triangles, and identify the vertices in sets of $3$ (belonging to distinct triangles, but making sure that you don't identify all the vertices of one triangle with those of another) so that you end up with $15$ distinct vertices.

FWIW, here are some pictures of the graph as constructed using Derek Holt's comment. The graph is not planar, and I don't know if there is a simpler way to visualize it.

enter image description here

enter image description here

share|cite|improve this answer
I was going to ask if you had a picture... and yet seeing this is strangely unsatisfying :). When you say the graph is not planar, do you mean the top and bottom pictures are not on the same plane? – tacos_tacos_tacos Oct 21 '12 at 17:19
Also, in the top picture, I noticed $V_(1,5)$ is connected to $V_(1,6)$ by an edge. Is this just a typo? – tacos_tacos_tacos Oct 21 '12 at 17:20
No, $V[1,5]$ is not connected by an edge to $V[1,6]$. What you're seeing in the top picture is the edge from $V[1,5]$ to $V[2,3]$ – Robert Israel Oct 21 '12 at 17:47
The 15 triangles are of the form $\{V[a,b],V[c,d],V[e,f]\}$ where $(a,b,c,d,e,f)$ is a permutation of $(1,2,3,4,5,6)$ with $a<b$, $c<d$, $e<f$. – Robert Israel Oct 22 '12 at 3:04
Of course you can think of the points as being associated with the 15 transpositions $(a,b)$ of $S_6$ and the 15 triangles with elements $(a,b)(c,d)(e,f)$ that are products of three disjoint transpositions. The outer automorphism of $S_6$ interchanges these two conjugacy classes in $S_6$. I don't know exactly how your project will continue, but you can see the connection now between your graph and the outer automorphism. – Derek Holt Oct 22 '12 at 8:18

Your Answer


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.