2-uniform hypergraphs do * not* obey the
Helly-property:
The sets {*a,b*}, {*b,c*}, and {*a,c*} have pairwise
nonempty intersection, but empty total intersection.
However, for simple hypergraph this is essentially
the only such example:

Every clique with more or less than 3 vertices in a line graph
is a star graph. |

This is the reason why the first step in the dualization-approach can be worked out, as we shall see.

We have to find out which 3-vertex cliques are star graphs and which not.
We assume *G* connected with more than 4 vertices.
Now every 3-vertex clique *C* which is a star graph has some vertex
outside adjacent to exactly one vertex of *C*.
On the other hand,
every 3-vertex clique which is no star clique does not have such a vertex.

The final task is to add all star graphs which are not cliques. These must be 2- or 1-vertex graphs. Note that every edge lies in exactly one star graph, and every vertex in exactly two, compare Krausz`s Theorem. Thus we first add all edges that are not covered by clique star graphs, and after that, we add all 1-vertex star graphs necessary.

Note that the second step in the dualization-approach is trivial---it is obvious how to check a hypergraph for simplicity and 2-uniformity.

In order to be an efficient algorithm, the first step,
checking all cliques, is still not performable.
There are graphs, though not line graphs,
with an exponential number of cliques.
One has to exclude these graphs by some rough sieve in advance.
One possibility is to check whether or not the graph in question
has some induced *K _{5}-e*---line graphs cannot have this,
but graphs without induced

There are quicker algorithms:

[R73]
[L74]:
There is some linear-time algorithm for recognizing
line graphs. |

Erich Prisner

made on January 12, 1999