Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a connected graph G which has n vertices and m edges. If m = n − 1, then we know immediately that G is a tree; which is notable because it has no cycles — between any two vertices, there is exactly one path. If m = n, we know that G contains exactly one cycle. And if m > n, we know that G has multiple cycles. (Note that m < n − 1 is impossible for connected graphs.)

Now consider a connected hypergraph H, where each edge contains exactly k vertices (it is k-uniform), where k ≥ 2. Is there any similar sort of structural property of H, or graph class to which H belongs, if it has exactly n edges? At most n − 1 edges?

More precisely: suppose that there is a mapping from the edges to the vertices, such that each edge is mapped to a distinct vertex to which it is incident. (If you look at the factor graph F of the hypergraph — a bipartite graph between a collection of "hyperedge-nodes" and "vertex nodes", where a hyperedge-node e is adjacent to a vertex-node v in F, if and only if e is an edge in H incident to v — then this is equivalent to there being a matching which covers the hyperedge-nodes.) Given that H which has such a mapping, suppose that the mapping is in fact bijective. Does this entail any important properties of H? What if this function is injective, but not surjective?

share|cite|improve this question
Note: there is at least one analogous property of hypergraphs to trees: if there are precisely $(n-1)/(k-1)$ edges, then there are still unique "paths" in the hypergraph between any pair of nodes; and again, fewer edges are impossible whilst remaining connected. However, I am hoping to find out properties which hold or which fail to hold with very close to n edges, if any are known. – Niel de Beaudrap Oct 5 '11 at 13:28
A clutter is a pair (V,E) where E is a collection of subsets of V each containing two or more vertices and harboring no containments. The density of a connected clutter C=(V,E) is $\kappa(C)=\sum_{e\in E}(|e|-1)-|V|$. A clutter C with two or more edges is a tree if $\kappa(C)=-1$. – Gus Wiseman Oct 8 '11 at 4:46
@GusWiseman: interesting! In the $k$-regular case, clutters are quite a natural subclass to consider. And it would seem that the pertinent property of clutter which is a tree is again acyclicity, that there are unique paths between any pair of vertices. However, this criterion does not compare number of edges, but their collective size; and indeed, in the $k$-regular case, the condition $\kappa(C) = -1$ is equivalent to $m = (n-1)/(k-1)$ for $n = |V|$ and $m = |E|$, which I describe in my preceding comment. – Niel de Beaudrap Oct 8 '11 at 10:35
For (V,E) a clutter consider the set of set partitions p of E whose set of unions Union^*(p) is a clutter that is tree. This poset has a unique maximum set partition s (but I haven't found an easy proof of this fact). The blocks of s are clutters that I call blobs. In other words, every clutter is a tree of blobs. Blobs are not characterized by density value or 2-connectedness, and I haven't found a way to enumerate them directly. But they can be defined as clutters with no contraction that is a tree. – Gus Wiseman Oct 8 '11 at 16:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.