TADM2E 5.5

From Algorithm Wiki
Revision as of 18:13, 11 September 2014 by Algowikiadmin (talk | contribs) (Recovering wiki)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Graphs with max degree 2, can be bipartite (even number of edges) or tripartite (odd number of edges)


Consider a triangle (3 edges, 3 vertices): it's not bipartite even though every node has an even number of edges and the graph has an even number of edges.



For such a graph, such that the degree of every vertex is at most 2, we can use a DFS traversal, coloring the child the opposite color of the parent. When we see a Back edge, we color the currently discovered child with a color different that the parent, and also different from the ancestor discovered through that back edge.

Since there is just one traversal, it runs in O(m + n) (m edges, n vertices)