The average order of a connected induced subgraph of a graph and union‐intersection systems.

Because connectivity is such a basic concept in graph theory, extremal problems concerning the average order of the connected induced subgraphs of a graph have been of notable interest. A particularly resistant open problem is whether or not, for a connected graph G $G$ of order n $n$, all of whose vertices have degree at least 3, this average is at least n ∕ 2 $n\unicode{x02215}2$. It is shown in this paper that if G $G$ is a connected, vertex transitive graph, then the average order of the connected induced subgraphs of G $G$ is at least n ∕ 2 $n\unicode{x02215}2$.The extremal graph theory problems mentioned above lead to a broader theory. The concept of a Union‐Intersection System (UIS) S ≔(P , B ) ${\mathscr{S}}:= (P,{\rm{ {\mathcal B} }})$ is introduced, P $P$ being a finite set of points and B ${\rm{ {\mathcal B} }}$ a set of subsets of P $P$ called blocks satisfying the following simple property for all A , B ∈ B $A,B\in {\rm{ {\mathcal B} }}$: if A ∩ B ∈ B $A\cap B\in {\rm{ {\mathcal B} }}$, then A ∪ B ∈ B $A\cup B\in {\rm{ {\mathcal B} }}$. To generalize results on the average order of a connected induced subgraph of a graph, it is conjectured that if a UIS is, in various senses, “connected and regular,” then the average size of a block is at least half the number of points. We prove that if a union‐intersection set system is regular, completely irreducible, and nonredundant, then the average size of a block is at least half the number of points. [ABSTRACT FROM AUTHOR]