Determine if G is bipartite. Find a maximal path and Eulerian circuit in G.

Question

Would I be correct to assume that a maximal path would be e-c-a-b-h-d-f-g? Is this my eulerian circuit: c-e-b-a-c-h-b-d-f-g-d-h-f-c?

Also, am I right to say it is not bipartite because it contains an odd cycle: triangle b-h-d?

Answer 1

You are correct about the not-bipartite argument. Any odd cycle will do, and you've found one, so that proof is complete. And I don't know what "maximal path" means to you, but if it means "a path going through as many vertices as possible, never using the same vertex twice", then that's good too. You've found a path that goes through every vertex, and thus it must be maximal.

As for Eulerian circuit, you can build one recursively. Start with any cycle, like b-h-d-b. Then note that when you're at h, you can insert a detour through c and f to get b-h-c-f-h-d-b. Then note that when you're at c, you can take a detour through a-b-e to get b-h-c-b-c-a-c-f-h-d-b. And so on.

Since each vertex has even degree, and the graph is connected, we can always add in these detours as long as there are edges we haven't traversed (in fact, this construction is one way to prove that each vertex having even degree is sufficient for the graph to be Eulerian).