# Triangular graphs

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.

-
It seems to me you want to start with a list of all the trisngles in the graph and prove a few things about what portion of the graph they cover and how they overlap. – hardmath Feb 14 '13 at 17:27
A good starting point would be to draw a few examples of triangular graphs for yourself to get a feeling for how they work. The intuitive observations you make will be candidates for lemmas you might be able to prove about triangular graphs in general. – Henning Makholm Feb 14 '13 at 17:46
I think what you want in $(c)$ is a 'maximum' matching, not maximal. – polkjh Feb 14 '13 at 17:58

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).

-

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.

-
I think the idea in (c) is not quite correct. Removing a maximal matching might give a spanning tree, but not every spanning tree can be obtained this way. So removing an arbitrary spanning tree doesn't necessarily give a matching. – polkjh Feb 14 '13 at 18:36
@polkjh Yeah, I think you ar right about that... – Thomas Andrews Feb 14 '13 at 19:06
If I use this algorithm to recognise a triangular graph...what kind of time complexity am I looking at. – ARi Dec 18 '15 at 6:57