On minimal blocks
Michael D. Plummer · Transactions of the American Mathematical Society · 1968
Introduction.A connected graph G is a block if there is no point v in G such that G-v is disconnected.A block G will be called block-line-critical (b.l.c.) if, for every line x in G, G-x is not a block.Such graphs occur repeatedly in the study of blocks-for example, when a proof by induction on the number of lines of a block is being attempted.Clearly, a cycle of any length is a b.l.c.graph.There are, however, b.l.c.graphs with a much more complex structure.In this paper several structural characterizations of b.l.c.graphs are obtained as well as a number of additional properties of such graphs.2. Additional terminology.For the sake of completeness, we introduce the following additional definitions.A graph G is a finite nonempty set V(G) of points together with a collection E(G) of lines each of which is an unordered pair of points.If x is the line containing the points u and v, we write x = uv and say that u and v are adjacent, x joins u and v, and that x is incident with points u and v. Two lines x and y which have a common point are also said to be adjacent.The complete graph on p points, Kp, is that graph with p points in which every two points are adjacent.A subgraph of G is a graph all of whose points and lines are also in G.The subgraph of a graph G generated by a set of lines X is that graph H whose set of lines is X and whose points are those points of G incident with a line of X.A path P is an alternating sequence of distinct points and lines, beginning and ending with points (said to be joined by P) such that each line is incident with the points before and after it.The first and last points in this sequence are called the endpoints of P, and all other points are termed intermediate.We shall have occasion to refer to a path P by its sequence of points; e.g., P=[ux, u2,..., «"].If P= [ux, u2,..., um] and Q = [vx, v2,..., v"] are two paths where the intermediate points of F are all distinct from the intermediate points of Q, um = vx, and either vn = ux or vn is distinct from every point ofP, we define a new path P+Q, the sum ofP and Q, to be that path with point sequence [ux, u2,..., um=vx, v2,..., vn]-A path of length ä 2 together with a line joining the first and last points is called a cycle.A path or a