Difference between revisions of "TADM2E 5.5"

Revision as of 18:13, 11 September 2014

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)