Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.