Mathematics desk
< June 7	<< May \| June \| Jul >>	June 9 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 8

Example of a graph

Can someone please give me an example of a k-regular connected graph G, (k>2) which has order 4 or more and contains a triangle but no square?-Shahab (talk) 06:14, 8 June 2011 (UTC)[reply]

I have an example of order 10, but I'm going to have to draw it. I did a quick search on Commons to see if there was already an image of it there, and I found the Markström graph (see right), which is another example. —Bkell (talk) 07:20, 8 June 2011 (UTC)[reply]

The Dürer graph is also an example. —Bkell (talk) 07:22, 8 June 2011 (UTC)[reply]

And Tietze's graph. (I'm running through the list at commons:Graphs in graph theory, by the way.) —Bkell (talk) 07:25, 8 June 2011 (UTC)[reply]

Three of the truncated Platonic solids, too. The truncated tetrahedron is pretty close to the example I came up with; here's a poor attempt to draw my example (the O's are the vertices):

   O---------O
  / \       / \
 /   \     /   \
O-----O   O-----O
 \     \ /     /
  \     O     /
   \    |    /
    \   O   /
     \ / \ /
      O---O

—Bkell (talk) 07:40, 8 June 2011 (UTC)[reply]