Special Graph Types: Bipartite, Complete, and Cyclic

Complete Graphs: Maximum Connectivity

The simplest special graph type to consider is one where every possible connection exists. This is called a complete graph.

A complete graph on $n$ vertices, denoted $K_n$, is a simple graph where every pair of distinct vertices is connected by a unique edge. Think of it as a network with maximum density, where everyone is directly connected to everyone else.

To see this in action, the following video provides a clear definition and shows what the first few complete graphs look like.

As you saw, $K_3$ is a triangle, $K_4$ is a square with its two diagonals, and so on. Given your data science background, you might recognize that the number of edges in $K_n$ is the same as the number of ways to choose 2 items from a set of $n$, which is given by the combination formula:

This quadratic growth in edges relative to nodes makes large complete graphs very dense.

Cycles and Cyclic Graphs: Loops and Paths

Next, we'll look at graphs that contain closed loops, which are fundamental structures in graph theory. It's important here to distinguish between two related terms: cycle graphs and cyclic graphs.

A cycle graph, denoted $C_n$, consists of a single cycle connecting $n$ vertices in a closed loop (where $n\ge 3$). Each vertex has a degree of exactly 2. It's the most basic form of a closed network.

A cyclic graph, on the other hand, is any graph that contains at least one cycle. Therefore, every cycle graph $C_n$ is also a cyclic graph, but not all cyclic graphs are cycle graphs. For example, a complete graph $K_4$ is cyclic because it contains several $C_3$ subgraphs (triangles), but it is not a cycle graph itself.

This distinction is subtle but important. The following image and reading will help clarify it.

Understanding cycles is essential for many algorithms. For instance, some algorithms only work on acyclic graphs (graphs with no cycles), such as trees. The presence of a cycle can mean that information can flow back to where it started, a key consideration for message passing in GNNs.

Bipartite Graphs: Two Sets of Nodes

The final category, bipartite graphs, is one of the most significant for machine learning applications.

A graph is bipartite if its vertices can be divided into two disjoint and independent sets, let's call them $U$ and $V$, such that every edge connects a vertex in $U$ to one in $V$. Crucially, no edge connects two vertices within the same set.

A classic real-world example is a user-item graph for a recommendation system. One set of nodes represents users ($U$), and the other set represents items like movies or products ($V$). An edge exists if a user has rated, viewed, or purchased an item. There are no edges connecting user-to-user or item-to-item directly in this model.

But how can you determine if an arbitrary graph is bipartite? The standard method is an algorithm called two-coloring. You attempt to "color" the graph with just two colors (say, blue and green) according to one rule: no two adjacent vertices can have the same color.

• If you can successfully color the entire graph this way, it is bipartite. The two sets of vertices are simply all the blue nodes and all the green nodes.
• If you find a contradiction—a situation where an edge connects two nodes that must have the same color—the graph is not bipartite.

The next video provides an excellent, detailed walkthrough of this process.

As the video demonstrated, this coloring process is a simple but powerful way to test for bipartiteness. An interesting consequence you can prove with this technique is that a cycle graph $C_n$ is bipartite if and only if $n$ is even. An odd-length cycle will always create a coloring contradiction.

Just as we have complete graphs, we also have complete bipartite graphs, denoted $K_{m,n}$. This is a bipartite graph with $m$ vertices in the first set and $n$ in the second, where every vertex in the first set is connected to every vertex in the second set.

The following short clip concludes the previous video by defining this type.

Conclusion

In this lesson, we classified graphs based on their high-level structure, identifying three important families. These structures are not just academic curiosities; they define the "shape" of data in many GNN applications and determine which algorithms are suitable.

Here are the key takeaways:

• Complete Graph ($K_n$): Every vertex is connected to every other vertex. It represents maximum density.
• Cycle Graph ($C_n$) vs. Cyclic Graph: A cycle graph is a single closed loop. A cyclic graph is any graph that contains one or more cycles.
• Bipartite Graph: The vertices can be partitioned into two sets where edges only connect vertices from different sets. They are common in matching and recommendation problems.
• Two-Coloring: A simple and effective algorithm to test if a graph is bipartite.
• Complete Bipartite Graph ($K_{m,n}$): A bipartite graph with all possible connections between the two vertex sets.

So far, we have focused on describing graphs—their components and their overall structure. In our next lesson, we will begin to operate on them. We will learn about Breadth-First Search (BFS), a fundamental algorithm for systematically exploring a graph's vertices and edges.