Kuratwoski’s First Graph and Second Graph

by

Kuratowski’s first graph usually refers to the non-planar complete graph on five vertices denoted by K5 whereas Kuratowski’s second graph K3,3 is the complete bipartite graph with two sets of 3 vertices which is also non-planar. Lets discuss about Kuratowski first and second graph with their properties.

What is Kuratwoski’s First Graph?

Definition: Kuratowski’s first graph, denoted as K5, is the complete graph with five vertices and ten edges where every vertex is connected to every other vertex.

Kuratwoski’s First Graph

Properties of Kuratwoski’s First Graph

  1. The Kuratowski first graph K5 has 5 vertices, every pair of vertices connected by an edge, total number of edges is $5C_2=10.$
  2. The graph K5 is non-planar.
  3. Chromatic number of Kuratowski’s first graph is 5, that is, $\chi$(K5) = 5.

What is Kuratwoski’s Second Graph?

Definition: Kuratowski’s second graph, denoted as K3,3, , is a specific non-planar, complete bipartite graph featuring six vertices and nine edges.

It is famously known as the “utility graph” (three houses connected to three utilities) and represents one of the two fundamental forbidden subgraphs in Kuratowski’s theorem for defining planar graphs.

Kuratwoski’s Second Graph

Properties of Kuratwoski’s Second Graph

  1. The Kuratowski second graph K3,3 is a bipartite graph. So it has two disjoint sets of vertices, each containing 3 vertices, every vertex in one set connected to every vertex in the other set, no edges between vertices in the same set.
  2. The graph has 6 vertices and 9 edges.
  3. The graph K3,3 is non-planar.
  4. Chromatic number of Kuratowski’s first graph is 5, that is, $\chi$(K3,3) = 2.

Also Study:

  1. Degree of a Vertex in Graph: Definition, Examples, Handshaking Theorem
  2. Simple Graph has Two Vertices of Same Degree: proof
  3. Prove that a tree with n vertices has (n-1) edges
  4. A graph is a tree if and only if it is minimally connected – Proof
  5. Simple Graph with n Vertices and k Components have at most (n-k)(n-k+1)/2 Edges
  6. Chromatic number of a complete graph with n vertices is n: Proof
  7. Chromatic number of a cycle with n vertices is 2 if n even and 3 if n odd

    Share via: