1. **Problem:** Can five houses be connected to two utilities without connections crossing? This is the classic "utilities problem" or the K_{3,3} bipartite graph problem.
2. **Explanation:** The problem asks if the bipartite graph K_{3,3} (3 houses and 3 utilities) is planar. A graph is planar if it can be drawn on a plane without edges crossing.
3. **Key fact:** K_{3,3} is a well-known nonplanar graph. It cannot be drawn without edges crossing.
4. **Reasoning:** By Kuratowski's theorem, K_{3,3} is one of the two minimal nonplanar graphs (the other is K_5). Therefore, five houses connected to two utilities (which forms K_{5,2} or a similar bipartite graph) cannot be drawn without crossings if it contains a K_{3,3} subgraph.
5. **Conclusion:** No, five houses cannot be connected to two utilities without connections crossing.
Final answer: **No, it is impossible to connect five houses to two utilities without crossings.**
Utilities Planarity 76098C
Step-by-step solutions with LaTeX - clean, fast, and student-friendly.