Content deleted Content added
refactor |
→Other graph-theoretic properties: missing smallest |
||
Line 52:
===Other graph-theoretic properties===
[[File:K33 one crossing.svg|thumb|upright=0.5|Drawing of <math>K_{3,3}</math> with one crossing]]
<math>K_{3,3}</math> is a [[triangle-free graph]], in which every vertex has exactly three neighbors (a [[cubic graph]]). Among all such graphs, it is the smallest. Therefore, it is the [[Cage (graph theory)|(3,4)-cage]], the smallest graph that has 3 neighbors for vertex in which the shortest cycle has length 4.{{r|coxeter}}
Like all other [[complete bipartite graph]]s, it is a [[well-covered graph]], meaning that every [[maximal independent set]] has the same size. In this graph, the only two maximal independent sets are the two sides of the bipartition, and obviously they are equal. <math>K_{3,3}</math> is one of only seven [[cubic graph|3-regular]] [[k-vertex-connected graph|3-connected]] well-covered graphs.{{r|cer93}}
| |||