View source for Xanthan ketal pyruvate transferase

[[File:Triple torus illustration.png|thumb|120px|[[Triple torus|Surface of genus 3]].]]
In the [[mathematics|mathematical]] field of [[graph theory]], the '''Klein graphs''' are two different but related [[regular graph]]s, each with 84 edges. Each can be embedded in the orientable [[surface]] of [[Surface#Classification_of_closed_surfaces|genus]] 3, in which they form [[dual graph]]s.

==The cubic Klein graph==
{{infobox graph
 | name = Klein graph
 | image = [[Image:Klein_graph.svg|250px]]
 | image_caption = The (cubic) Klein graph
 | namesake = Felix Klein
 | vertices = 56
 | edges = 84
 | automorphisms= 336
 | girth = 7
 | radius = 6
 | diameter = 6
 | chromatic_number = 3 
 | chromatic_index = 3
 | properties = [[Symmetric graph|Symmetric]]<br>[[Cubic graph|Cubic]]<br>[[Hamiltonian graph| Hamiltonian]]<br>[[Cayley graph]]
}}

This graph is a 3-[[regular graph]] with 24 vertices and 84 edges, named after [[Felix Klein]].

It is a [[Hamiltonian graph]]. It has [[chromatic number]] 3, [[chromatic index]] 3, radius 6, diameter 6 and [[girth (graph theory)|girth]] 7. It is also a 3-[[k-vertex-connected graph|vertex-connected]] and a 3-[[k-edge-connected graph|edge-connected]] graph.

It can be embedded in the [[Manifold#Genus_and_the_Euler_characteristic|genus]]-3 orientable [[Manifold|surface]] (which can be represented as the [[Klein quartic]]), where it forms the "Klein map" with 24 heptagonal faces, [[Schläfli symbol]] {7,3}<sub>8</sub>.

According to the ''Foster census'', the Klein graph, referenced as F056B, is the only cubic symmetric graph on 56 vertices which is not [[Bipartite graph|bipartite]].<ref>{{citation
 | last1 = Conder | first1 = M. | author1-link = Marston Conder
 | last2 = Dobcsányi | first2 = P.
 | journal = J. Combin. Math. Combin. Comput.
 | pages = 41–63
 | title = Trivalent symmetric graphs up to 768 vertices
 | volume = 40
 | year = 2002}}.</ref>

It can be derived from the 28-vertex [[Coxeter graph]].<ref>{{cite web|last=Dejter|first=Italo|title=From the Coxeter graph to the Klein graph|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.188.2580|publisher=CiteSeer|accessdate=23 March 2013}}</ref> 

===Algebraic properties===
The automorphism group of the Klein graph is the group PGL<sub>2</sub>(7) of order 336, which has
[[(2,3,7) triangle group|PSL<sub>2</sub>(7)]] as a normal subgroup. This group acts transitively on its half-edges, so the Klein graph is a [[symmetric graph]]. 

===Gallery===
<gallery>
Image:Kleinh.svg| Alternative drawing of the cubic Klein graph, showing that it is Hamiltonian, with [[chromatic index]]&nbsp;3.
</gallery>

== The 7-valent Klein graph ==

{{infobox graph
 | name = Klein graph
 | image = [[Image:Klein-graph-7-valent_Hamiltonian.svg|250px]]
 | image_caption = The (7-valent) Klein graph
 | namesake = Felix Klein
 | vertices = 24
 | edges = 84
 | automorphisms= 336
 | girth = 3
 | radius = 3
 | diameter = 3
 | chromatic_number = 4 
 | chromatic_index = 7 
 | properties = [[Symmetric graph|Symmetric]]<br>[[Hamiltonian graph| Hamiltonian]]
}}

This graph is a 7-[[regular graph]] with 56 vertices and 84 edges, named after [[Felix Klein]].

It is a [[Hamiltonian graph]]. It has [[chromatic number]] 4, [[chromatic index]] 7, radius 3, diameter 3 and [[girth (graph theory)|girth]] 3. <!--It is also a 3-[[k-vertex-connected graph|vertex-connected]] and a 3-[[k-edge-connected graph|edge-connected]] graph.-->

It can be embedded in the genus-3 orientable surface, where it forms the dual of the "Klein map", with 56 triangular faces, [[Schläfli symbol]] {3,7}<sub>8</sub>.<ref>{{cite journal
  |last1=Schulte
  |first1=Egon
  |last2=Wills
  |first1=J. M.
  |title=A Polyhedral Realization of Felix Klein's Map {3, 7}<sub>8</sub> on a Riemann Surface of Genus 3
  |journal=J. London Math. Soc.
  |year=1985
  |volume=s2-32
  |issue=3
  |url=http://jlms.oxfordjournals.org/content/s2-32/3/539.abstract}}</ref>

===Algebraic properties===
The automorphism group of the 7-valent Klein graph is the same group of order 336 as for the cubic Klein map, likewise acting transitively on its half-edges.

The [[characteristic polynomial]] of the Klein graph is equal to <math>(x-7) (x+1)^7 (x^2-7)^8</math>.<ref>{{cite web|last=Weisstein|first=Eric|title=Klein graph|url=http://mathworld.wolfram.com/KleinGraph.html|work=MathWorld|publisher=Wolfram Research|accessdate=23 March 2013}}</ref>

== References ==
<!-- http://webcache.googleusercontent.com/search?q=cache:3tOQpsJ0YCIJ:www.math.auckland.ac.nz/~conder/preprints/cubic768.ps+&cd=1&hl=en&ct=clnk&gl=uk
-->
{{reflist}}

[[Category:Individual graphs]]
[[Category:Regular graphs]]