Shaka and the giraffes

by Dinoj Surendran

It was one of those extremely hot days. One of those days when half the animal population were at --- correction, in --- their local branch of the river, with the other half forming a rather impatient waiting list. One of those days when nobody felt like moving.

But Shaka was not nobody. On the contrary, he was just getting used to the fact that he was the undisputed master of a very large piece of territory, having conveniently disposed of his arch-enemy Zwide the previous day. Now he could relax and do all those other things that he had always dreamt of and never had the time to do.

Trouble was, the only thing he'd ever dreamt of was becoming the undisputed master of a very large piece of territory and disposing of --- well, you get the idea.

''Hey guard!'' he called to the nearest soldier, who promptly stood at a very attentive attention. ''go get me General Adnawat.''

The soldier, having expertly concealed a slight raising of his eyebrows, rushed off and soon the said general was standing before his master. He asked how he could serve the king.

''There's no need to flatter me, general. My fortune teller tells me there's a while to go before I go mad, so you can feel quite safe. My congratulations on taking care of business yesterday --- I am told you did a brilliant job. Even though you spent half the day looking up at the sky while a raging battle swirled around you.''

''Actually I was thinking about a few theorems on graphs.''

''Giraffes? My third best general spent half a day gazing at clouds and thinking of giraffes? No, don't bother explaining. I suppose it's got something to do with those silly symbols you're always playing with. The battle was won and that is all that matters. I want to discuss tomorrow's competition.''

The competition in question was the final of the annual wrestling contest featuring two well-muscled representatives of homo densus densus trying to get each other flat on the ground before the other did.

''Not too bad --- I'm told they have planned the fight to give the maximum pleasure to the audience.''

''Excellent. And the great race?''

''Well, if you ignore everything imperfect, then everything's perfect.''

''Whenever you say something like that, I know something's wrong. What is it this time?''

Adnawat bent down (he was already crouched before Shaka so it was a minor rearrangement of his limbs) and drew a map of the course in the sand.

''Right,'' said the general, ``the competitors start and finish at your hut. They must run on all the seven routes shown and swim from Palebe's point to Malebe's point (or vice versa). The interesting thing about this race is that the runners can choose the order of the sections they tackle, so long as they do each section. I have personally tested the route and I know it's the ultimate in endurance. So I feel that no competitor should have to do any section twice.''

''So?''

''The trouble is, with this route, they have to do one section twice even in the best case.''

''Yes, that could be a problem.'' Shaka looked thoughtful for a moment before speaking again, ''But how did you come to that conclusion?''

For the first time in the meeting, the general looked uncomfortable. ''Well, sir, if you really must know (and it was pretty obvious that that was the case), I used graphs.''

''Giraffes?'' Shaka wondered if it would be elephants next. Or lions.

''Okay, giraffes. You see, we can represent the map in a different way:''

''We have replaced each landmark by a dot and drawn a line between two dots whenever there was a route between the corresponding landmarks. So what the competitors must do is go across each line exactly once and return to the starting point.''

''Where are the giraffes?''

''Well, that whole combination of dots and lines is called a giraffe.''

''That's absolutely stupid. Giraffes don't look like that.''

Adnawat wondered if he should explain that the said combination was called a graph and not a giraffe, but decided against it. He nodded his head like someone absolutely stupid and went on.

''We can do this because there is no fundamental difference between the landmarks for the competitors. Likewise for the lines --- it makes no difference that some are run, others are swum --- all that matters is that they must be traversed.''

''But they start and finish at my hut!''

''That is correct, sir. And we will keep that in mind. May I continue?''

Shaka wasn't sure if he was interested in all this giraffe business, but as the alternative was another boring afternoon in the blazing sun, he didn't feel he had much choice.

''Suppose such a way exists. We start at the dot representing your hut and follow this way till we have travelled on all lines. Can you see that we will come `into' and `out of' each dot the same number of times?''

Shaka looked. And cerebrated. And agreed.

''So each dot must have an even number of lines attached to it.''

Shaka agreed again. Adnawat had explained to him previously about even and odd numbers and he had a very good memory.

''Now look at our giraffe. Does each dot have an even number of lines? No. The two dots at the top are each attached to three lines. This means that in our original map, no competitor would be able to cross each section exactly once and both start and end up at your hut.''

''I see. Well, couldn't we make all the dots have an even number of lines attached to them?''

''Easily. We could remove that route between your hut and Malebe's point. Or we could add yet another route there. Or we could remove the route from your hut to the Cave and add a route from the Cave to Malebe's point...''

''That last one sounds best. So now we have an even number of lines coming from each dot. Is that enough to solve our problem?''

''Fortunately, yes. That has been proved by somebody (actually, Carl Hierholzer, a German lecturer who died in 1871 when still in his twenties) who hasn't been born yet in the land where the big ships and bad smells come from. He said that once you have a map with all dots having an even number of lines, you can do the following: Start at any dot. Then travel across each line. Imagine that the line disappears after you use it. If you always make sure that you never cause the map to be in two disconnected parts, then you will eventually travel across each line (once) and get back to your starting point.''

''That's good. Change the route accordingly. You may leave.''

Adnawat, after perfoming an abbreviated version of the ceremony of leaving the king --- he had just received an urgent call from nature --- fled to the appropriate bushes.

Shaka thought about the giraffes. Why, he asked himself, did Adnawat have to go through all that fuss just to prove something so simple? Why did he always have to represent something real by something imaginary? Landmarks by dots, for example. Finally, in a brilliant feat of mental calisthenics, he came to a conclusion. Adnawat belonged to an lunatic asylum. He heard they were called universities in the West. He turned his mind to more constructive matters. Drawing pictures in the sand.

Darn those pictures --- He'd been trying to draw them since his younger days. He winced at the memories of his childhood, and shrugged them off. He wanted to draw the shapes in one go without lifting his stick off the ground and without retracing any lines. And finishing where he began. Wait a minute, that sounded familiar... too familiar! He placed dots wherever lines met. Aha!

In no diagram did all dots have an even number of lines coming from them --- and thus none of them could be drawn in the required manner. But the arrow? He could draw it fully without lifting his stick --- oh, but he wasn't ending where he started. Hmmmm, he thought, perhaps he could find out what would happen if only two dots had an odd number of lines attached to them? On second thought, he didn't feel like thinking till the next issue.