To prove that any undirected graph $G = (V, E)$ with at least two nodes has some orientation that is a Directed Acyclic Graph (DAG) where $a$ is a source and $b$ is a sink, we proceed as follows:

---

1. Understanding the Requirements

• An orientation of $G$ means assigning a direction to each edge $u \edg v$ such that it becomes either $u \to v$ or $v \to u$, but not both.
• A DAG (Directed Acyclic Graph) is a directed graph with no directed cycles.
• Node $a$ being a source means all edges incident to $a$ are directed away from $a$ (no incoming edges at $a$).
• Node $b$ being a sink means all edges incident to $b$ are directed toward $b$ (no outgoing edges from $b$).

We aim to construct an orientation of $G$ that satisfies all these conditions.

---

2. Orientation Strategy

1. Choose a Topological Order: A topological order of the vertices of a graph is an arrangement $v_1, v_2, \dots, v_n$ such that for every directed edge $u \to v$, $u$ appears before $v$ in the ordering. If $G$ has no cycles, such an order exists.

   Start by choosing a topological ordering $v_1, v_2, \dots, v_n$ of $V$ where $a$ is the first vertex ($v_1 = a$) and $b$ is the last vertex ($v_n = b$).

2. Orient Edges Based on Topological Order: For each undirected edge $u \edg v \in E$, orient the edge $u \to v$ if $u$ comes before $v$ in the topological order. Specifically:

   • If $u = a$, orient $a \to v$ for all $v$ adjacent to $a$.
   • If $v = b$, orient $u \to b$ for all $u$ adjacent to $b$.

3. Resulting Graph is a DAG: By construction, the orientation follows the topological order. Since no edge points backward in the order, no directed cycle can exist.

4. Ensure $a$ is a Source and $b$ is a Sink:

   • $a$ is the first vertex in the topological order, so all edges incident to $a$ are directed away from $a$.
   • $b$ is the last vertex in the topological order, so all edges incident to $b$ are directed toward $b$.

---

3. Formal Proof

Existence of a Topological Order

• Start with any spanning tree $T$ of $G$. Root the tree at $a$, and define a topological order by performing a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from $a$. Assign numbers to vertices as they are first visited.
• In this order:
  • $a$ will be the first vertex (root of the spanning tree).
  • $b$ will appear last as it is distinct from $a$.

Acyclicity

• If an orientation is assigned based on this topological order, no directed edge points backward. Thus, there are no directed cycles, and the resulting graph is a DAG.

Properties of $a$ and $b$

• By construction, $a$ is a source since all edges incident to $a$ point away.
• Similarly, $b$ is a sink since all edges incident to $b$ point toward $b$.

---

4. Conclusion

We have shown that it is possible to orient the edges of $G$ to form a DAG where $a$ is a source and $b$ is a sink.

---

Would you like further details on any step? Here are some related questions:

1. What is a detailed example of constructing such an orientation for a specific graph?
2. How does the proof ensure there are no directed cycles?
3. How can we compute a topological order for a graph algorithmically?
4. Can we generalize this proof for $k$-many sources or sinks?
5. What is the computational complexity of finding such an orientation?

Tip: When working with orientations, always check for cycles using the topological ordering approach!