判断n,m≥2的完全二部图$K_{n,m}$可定向性的方法求证

Awesome question! Your hunch that every complete bipartite graph $K_{n,m}$ (with $n,m \geq 2$) admits a strongly connected orientation is totally correct, and your plan to use induction plus circuit-based construction is a perfect, intuitive approach. Let’s walk through this clearly.

First: Clarify What "Orientable" Means Here #

When we talk about a graph being "orientable" in this context, we mean we can assign a direction to every undirected edge such that the resulting directed graph is strongly connected—any vertex can reach any other vertex via a directed path.

1. Your Core Idea is Valid: Induction + Circuit Construction #

Your intuition to combine induction with building up from circuits works because complete bipartite graphs are dense enough to let us extend smaller strongly connected orientations to larger ones, and circuits are the building blocks of strong connectivity.

Step 1: Base Cases #

Let’s start with small, concrete examples to confirm the base case:

• $K_{2,2}$: This is a 4-cycle. Orient it as a directed cycle (e.g., $x_1 \to y_1 \to x_2 \to y_2 \to x_1$)—obviously strongly connected.
• $K_{2,3}$: First build a directed circuit covering 2 vertices from each partition: $x_1 \to y_1 \to x_2 \to y_2 \to x_1$. Then for the third $y$-vertex $y_3$, add $x_1 \to y_3$ and $y_3 \to x_2$. Now every vertex can reach every other: $x_1$ gets to $y_3$ directly, $y_3$ reaches $x_2$ directly, and $x_2$ can reach $y_1$ via the original circuit, etc.

Step 2: Induction Hypothesis #

Assume that for all complete bipartite graphs $K_{n',m'}$ where $2 \leq n' \leq n$ and $2 \leq m' \leq m$, there exists a strongly connected orientation.

Step 3: Induction Step (Extending to $K_{n+1,m}$) #

Take $K_{n+1,m}$, with partitions $X = {x_1, x_2, ..., x_{n+1}}$ and $Y = {y_1, y_2, ..., y_m}$.

• By our induction hypothesis, $K_{n,m}$ (using $X' = X \setminus {x_{n+1}}$ and $Y$) has a strongly connected orientation $D$.
• Now we need to orient the edges from $x_{n+1}$ to all vertices in $Y$:
  • Pick at least one vertex $y_a \in Y$ and orient the edge as $x_{n+1} \to y_a$ (gives $x_{n+1}$ an outgoing path into the existing strong component).
  • Pick at least one vertex $y_b \in Y$ (can be different from $y_a$) and orient the edge as $y_b \to x_{n+1}$ (gives the existing strong component an incoming path to $x_{n+1}$).
  • For the remaining edges between $x_{n+1}$ and $Y$, you can orient them arbitrarily—no need to overcomplicate it.

Verify Strong Connectivity

• Between $x_{n+1}$ and any $x_i \in X'$: $x_i$ can reach $y_b$ via the strong orientation $D$, then take $y_b \to x_{n+1}$. Conversely, $x_{n+1}$ can reach $y_a$ directly, then take the path from $y_a$ to $x_i$ in $D$.
• Between $x_{n+1}$ and any $y_j \in Y$: If we oriented $x_{n+1} \to y_j$, a direct path exists. If we oriented $y_j \to x_{n+1}$, $x_{n+1}$ can reach $y_a$, then take the path from $y_a$ to $y_j$ in $D$.
• Within $X'$ or $Y$: Already guaranteed by the strong orientation $D$.

The same logic applies if we extend to $K_{n,m+1}$—just add the new $y$-vertex with at least one incoming and one outgoing edge to $X$.

2. Circuit Construction Alternative (More Visual) #

If you prefer a more hands-on, circuit-focused proof instead of induction:

1. Build a core circuit: For any $K_{n,m}$, pick a subset of vertices that forms a cycle (e.g., $x_1 \to y_1 \to x_2 \to y_2 \to x_1$ for $n,m \geq 2$).
2. Attach remaining vertices: For every leftover vertex (say $x_k \in X$), connect it to the core with at least one incoming edge (from some $y \in Y$ in the core) and at least one outgoing edge (to some $y' \in Y$ in the core). Do the same for leftover $y$-vertices.
3. Orient remaining edges arbitrarily: The dense nature of $K_{n,m}$ means you have plenty of edges to work with, so you’ll never run out of options to add those critical in/out paths.

This works because every vertex is tied into the core circuit, so any vertex can reach the circuit, then traverse it to reach any other vertex connected to the circuit.

Final Takeaway #

Your initial approach is spot-on. Both induction and circuit-based construction are valid ways to prove that all $K_{n,m}$ (with $n,m \geq 2$) are strongly orientable. The key reason this works is the density of complete bipartite graphs—you always have enough edges to ensure every vertex has both incoming and outgoing connections to the rest of the graph, which is the foundation of strong connectivity.

内容的提问来源于stack exchange，提问作者user496388