Three utilities problem: Difference between revisions

Revision as of 07:42, 30 November 2021

Revision as of 07:45, 30 November 2021

Line 42:

===Other graph-theoretic properties===

<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 3three neighbors per vertex and in which the shortest cycle has length 4four.{{r|tutte}}

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 of equal sizes. <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}}

===Generalizations===