Complete Bipartite Graphs

Introduction

• Focus: Introduction to complete bipartite graphs
• Previous discussions: Covered in other lessons, future discussions planned
• Definition: Bipartite graphs with every possible edge

Bipartite Graphs

• Graph G: Vertex set V, edge set E
• Definition: Partition vertex set into two sets (v1 and v2) such that:
  • Every edge joins a vertex in v1 with a vertex in v2
  • No edge joins two vertices within the same set
• Partite Sets: Sets in the partition, V = V1 ∪ V2
• Properties:
  • Each element of V is in exactly one partite set
  • No common elements between sets

Example: Bipartite Graph

• Six Vertices: Colored in two different colors
• Edges: White edges joining some orange and green vertices
• Partition: Vertex set into V1 (orange) and V2 (green)
• Edges: All edges from one partite set to the other
• Independent Vertex Set: No two vertices in the same set are adjacent

Complete Bipartite Graph

• Definition: Bipartite graph with every possible edge
• Properties:
  • Every pair of vertices in different partite sets must be joined by an edge
• Example: Adding necessary edges to form a complete bipartite graph
  • Vertices in one partite set adjacent to all vertices in the other partite set

Regularity in Complete Bipartite Graphs

• 3-Regular Example: Each vertex in one partite set is adjacent to 3 vertices in the other set
• Non-3-Regular: If vertices are removed
  • Degree of vertex will depend on the size of the opposite partite set

Notation

• K extsubscript{n}: Complete graph on n vertices
• K extsubscript{m,m}: Complete bipartite graph
  • Example: K extsubscript{3,1} or K extsubscript{1,3}
  • One partite set has 3 vertices, the other has 1
  • Example: K extsubscript{3,2}
  • Vertices in one set have a degree equal to the cardinality of the other partite set

Questions to Consider

• Edge Count: Number of edges in K extsubscript{m,n}
• Hamiltonian Graphs: Identify which complete bipartite graphs are Hamiltonian
  • Linked to a previous lesson on Hamiltonian graphs

Conclusion

• Support: Thanks to patrons and supporters
• Encouragement: Subscribe for more math lessons
• Special Thanks: To Valo for music used in lessons (links in the description)