A set of points M is said to
cover a graph G if every line in G has at least one point in M. Call M a minimum
cover (m.c.) for G if it is a point cover with a minimum number of points. The
number of points in any minimum cover of a graph G is called the point covering
number of G and is denoted by α(G). If x is a line in G, denote by G − x the graph
obtained from G by deleting x. Similarly, if v is a point of G,G−v will denote
the graph obtained from G by deleting v and all lines incident with v. A
line x in G is said to be a critical line (with respect to point covering) if
α(G − x) < α(G). A graph is called line-critical if every line is critical. Obviously
every complete graph is line-critical, and so is any odd cycle. There are,
however, many other line-critical graphs. The main purpose of this paper is
to prove that in any graph, two adjacent critical lines must lie on an odd
cycle. This result will imply that a line-critical graph must be a block and
furthermore, that any two adjacent lines in such a graph must lie on an odd
cycle.
