Triangular graphs

Question

I was learning algorithms and data structures, and can't manage with this problem:

We say that a graph is triangular when it is undirected, connected and it's each biconnected component is a cycle of length $3$.

a) Prove that each triangular graph is $3$-colorable (in terms of coloring vertices, of course).

b) Suggest an effective algorithm for $3$-coloring of a triangular graph.

c) Suggest an effective algorithm for finding maximum matching in triangular graphs.

I think a) can be approached with induction, but tried and I don't see it. For b) and c) no idea. Can anybody help? I really want to finally solve some graph theory problems, but they are so hard.

Answer 1

Notice that these graphs will have a tree like structure in terms of the triangles. That is, build a new graph with each triangle as a vertex and an edge between vertices if the corresponding triangles have a common node. We can show that this graph is a tree. With this structure, we can solve the given problems.

Hints:

a,b: Just start with some triangle, assign 3 different colours to its nodes. Then move to a neighbouring triangle (sharing one vertex) and assign colours to the 2 new vertices appropriately. Show that you can just proceed this naive way and get a valid 3-colouring.

c: In the tree seen above, pick a terminal vertex (vertex with degree 1) and consider the corresponding triangle. Try to show that you can always build a maximum matching starting with a particular edge in that triangle. Then pick that edge, remove the triangle and repeat this process (pick another terminal vertex in the new tree etc).

Answer 2

Hint for (a): Pick a triangle, and remove all its edges. Prove you are left with a graph with three disconnected components, and that each component is triangular or a single node. Proceed by induction.

This also yields (b), assuming finding a triangle can be done "effectively."

A useful property to prove is that if $G$ is triangular, then any edge $e$ of $G$ is on exactly one triangle.