Example: Recognizing line graphs

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₅-e---line graphs cannot have this, but graphs without induced K₅-e have few cliques, which can be generated in polynomial time.

There are quicker algorithms:

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