Skip to main content

Representing Special Graphs

What This Concept Is​

A DAG has no directed cycle and admits a topological order. An undirected tree is connected and acyclic; a forest is a disjoint union of trees. A bipartite graph admits two sides such that every edge crosses sides. A simple undirected complete graph on n vertices has n(n-1)/2 edges.

Planarity is the existence of a crossing-free embedding, not a drawing's appearance. For a connected plane graph, V-E+F=2 including the outer face. With c connected components, V-E+F=1+c. The bound E<=3V-6 requires a simple planar graph with V>=3; loops and parallel edges cannot be silently included in that bound.

Why It Matters Here​

Verified structure can permit simpler algorithms. DAG shortest paths allow negative edges because topological processing has no cyclic dependency. A tree has a unique simple path between vertices. Bipartite matching admits a flow reduction that does not apply unchanged to arbitrary nonbipartite graphs.

Concrete Examples​

For undirected edges 0–1,1–2,2–3, coloring 0 and 2 left, 1 and 3 right works. Adding 3–0 preserves bipartiteness; adding 2–0 creates an odd cycle and invalidates it. A self-loop immediately conflicts with two-coloring. In a disconnected graph, restart coloring in every unvisited component, including isolated vertices.

A directed 0→1→2→0 cycle is not a DAG even if a picture resembles a triangle with an apparent left-to-right layout. Labels and drawing positions are not proofs.

Common Confusion / Misconceptions​

V-1 edges alone do not prove a graph is a tree without connectivity or acyclicity. Tree edges from a directed DFS form a traversal forest but do not compute weak or strong components merely by grouping DFS roots. A DAG is not necessarily a tree, and planar does not imply bipartite.

How To Use It​

Turn special-structure assumptions into validations or explicit caller preconditions. Kahn's algorithm can validate acyclicity while ordering; two-coloring can produce a conflict witness. Keep planarity and geometric graph algorithms as optional extensions rather than assuming a sparse drawing certifies them.

Check Yourself​

  1. Which assumptions are needed for E<=3V-6?
  2. Why does V-1 alone not prove a tree?
  3. Why must two-coloring restart across components?
  4. What does a conflicting same-color edge establish?

Mini Drill or Application​

Give a disconnected graph with V-1 edges that is not a tree. Produce a DAG whose underlying undirected graph contains a cycle. Test a bipartite checker on an isolated vertex, an even cycle, an odd cycle and a self-loop. See P3.

Read This Only If Stuck​

Find trees, DAGs, bipartite graphs, and planar-graph assumptions in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.