2
$\begingroup$

I don't know graph theory, but I want to study this specific question for a while. I have no idea if this is a well known and studied question or not. I found it very difficult, and I don't know where to start, so I would be happy if you can give me a hint at least if it is not known.

My question is: I have a graph, such as chess board $9\times 9$, $n = 81$ points.

The total number of edges is $144$, or average connections is $144/81 \approx 1.8$.

I want to know how many $4$ edge long (with $5$ different points) subgraphs there are.

If its formula is not known, can we approximate the number of $7$ edge long subgraphs, if say $n$ is about $5000$, average connections is $5$ ?

$\endgroup$
7
  • $\begingroup$ In a simple graph one has the Handshake Lemma, which tells us the number of edges is half the sum of degrees over all the vertices. The title suggests a rather broad topic, while the body of the Question focuses on subgraphs of a particular "chess board" graph. The particular Question (4 edges, 5 vertices) is tractable, because having one more vertex than edges requires any connected subgraph be a tree. Can you clarify what you actually would like to have answered here? $\endgroup$ – hardmath Apr 16 '15 at 16:45
  • $\begingroup$ I gave chessboard an example, it may be a random graph. but I am wondering the answer of an average case. 10000 points, an average of 6 connections, what is the number of 12 edge subgraphs. I want to learn this. First I assumed it should be known, then I thought, it is very hard, maybe there is not a formula for this. anyway, you said "The particular Question (4 edges, 5 vertices) is tractable, because having one more vertex than edges requires any connected subgraph be a tree" How can i know this? Where should i start, which subjects of graph theory, to answer this question ? $\endgroup$ – xcvbnm Apr 16 '15 at 17:05
  • $\begingroup$ I will solve the specific problem, but without a "master graph" (like the chess board), I don't know how to define an average case. $\endgroup$ – hardmath Apr 16 '15 at 17:09
  • $\begingroup$ Thanks that will be a good start for me, then i can study it myself to generalize. $\endgroup$ – xcvbnm Apr 16 '15 at 17:17
  • $\begingroup$ A similar kind of Question, restricted to counting non-crossing "rope" paths between two points, was proposed here: How many possibilities to arrange a rope of length $n$ between two points?. The poster of that Question was also disappointed to learn there would be no exact formula, though as I pointed out in my response, if self-intersections were allowed, it would make the counting easier. $\endgroup$ – hardmath Apr 17 '15 at 14:30
1
$\begingroup$

We will count certain connected subgraphs of a "master graph" like a chess board, namely a rectangular grid of size $m\times n$ vertices (rows by columns) with $m\cdot(n-1)$ horizontal and $(m-1)\cdot n$ vertical edges.

All of our graphs will be simple, i.e. the edges are undirected and may be identified by an unordered pair of distinct vertices. Thus there are no "loops" (self-edges from a vertex to itself) nor multiple edges between the same pair of vertices.

More precisely we are counting labelled subgraphs, treating as distinct two subgraphs unless they consist of exactly the same vertices and edges. [If instead we wanted count isomorphic subgraphs only once, we would refer to them as unlabelled subgraphs.]

We make free use of polynomials involving terms like $(m-w)$ and $(n-h)$, but strictly speaking these should be replace by zero if $m \lt w$ or $n \lt h$, as there is no room on the board in those cases for some or all subgraphs. To avoid awkward repetition it will be assumed for the sake of the particular problem here that $m,n \ge 4$, so that all the polynomials are valid without further qualification.

Using the methods outlined below, I created a spreadsheet with $m,n$ as parameters and a row for each (connected) subgraph configuration. The final total number of connected 5-nodes, 4-edge subgraphs on a $9\times 9$ board is $4483$.


A tree is a connected graph with no cycles. This especially relates to the subgraphs we want to count, having four edges and five vertices, because a tree with $k$ vertices always has $k-1$ edges. Conversely, a connected graph with $k$ vertices and $k-1$ edges has no cycles and so is actually a tree.

A particularly nice case to start our counting is a "central" vertex connected to four different "leaf" vertices:

symmetric five point stencil

Such a subgraph can be placed on the chess board anywhere that a $2\times 2$ square could be placed, so there are $(m-2)\cdot (n-2)$ of these. It is especially symmetric in that rotations and reflections within the $2\times 2$ square do not generate any additional subgraphs.

We should pause to address an important point: How will we know if all the possible cases are shown and properly counted? For this we need some systematic methods of distinguishing and classifying cases.

A very useful concept for this is a degree sequence which is a descending sequence of nonnegative integers that corresponds to the number of edges incident to the different vertices of a graph. The case described above happens to coincide with subgraphs having a degree sequence $4+1+1+1+1$, since any vertex of degree four in a connected graph of five vertices necessarily takes this form.

The subgraphs of interest here have four edges, and the Handshaking Lemma or degree sum formula tells us that the sum over a corresponding degree sequence will be twice four or eight.

Not every quintuplet of nonnegative integers that sum to eight can be the degree sequence of a graph. For example $5+3+0+0+0$ cannot be realized. But there are efficient algorithms for deciding if a degree sequence is feasible, and in our problem the possible degree sequences can be quickly found.

The other feasible degree sequences are $3+2+1+1+1$ and $2+2+2+1+1$. These two cases involve a number of asymmetric configurations, but they at least provide a way of classifying those configurations.

Degree sequence 3+2+1+1+1

A method of counting subgraphs will now be applied to the case where the maximum degree is $3$, which amounts to the following cases (up to reflection and rotation) having degree sequence $3+2+1+1+1$.

third degree configurations

Each of these cases has a minimum "box" or containing frame, within which the subgraph can be reflected. When the box is square (as it is for the final two figures), the subgraph can also be rotated within the box, but if the box is rectangular, then a quarter rotation requires the box to be rotated (or "transposed") as well. In any case we can count all possible ways to place the box in the chess board, and respectively the ways to place the subgraph in the box.

The leftmost figure, a "chair" or "h", just fits into an upright $2\times 1$ box as shown or in quarter rotation a $1\times 2$ transposed box. The upright box can be placed on the chess board in $(m-2)\cdot (n-1)$ locations, while the transposed box goes onto $(m-1)\cdot (n-2)$ locations. Each box allows four distinct reflected/half-rotated versions of the subgraph, so the total number of subgraphs under this specific figure is:

$$ 4(m-2)\cdot (n-1) + 4(m-1)\cdot (n-2) $$

The next figure, very like a capital "F", has the same size boxes and symmetries within those boxes. Thus it gives the same total number of subgraphs as the first figure.

The third figure, perhaps viewed as "y" with a little imagination, fits into a $3\times 1$ box. Thus the upright box has $(m-3)\cdot (n-1)$ board locations, and the transposed box has $(m-1)\cdot (n-3)$ locations. After rotations and reflections, there will be a total number of these subgraphs:

$$ 4(m-3)\cdot (n-1) + 4(m-1)\cdot (n-3) $$

The fourth figure, best called "T" no doubt, fits into a $2\times 2$ square box. It has $(m-2)\cdot (n-2)$ board locations, and because of its bilateral symmetry, four distinct rotations within the square box. The total number of these subgraphs is:

$$ 4(m-2)\cdot (n-2) $$

The fifth possibility is an awkward figure for which I can suggest only "plow" as mnemonic. It fits in a $2\times 2$ square box but has no symmetry, and thus yields a full 8-fold dihedral orbit under rotation/reflection. It thus contributes the following total number of subgraphs:

$$ 8(m-2)\cdot (n-2) $$

Degree sequence 2+2+2+1+1

The remaining cases (no degrees above two) are subgraphs that are simple paths. There are nine such configurations to account for:

second degree configurations

By now the procedure for counting each of the congruent copies of these figures should be clear. The minimum bounding box of a figure is found, e.g. a $4\times 0$ box for the first figure, a straight path of length $4$. The rotations and reflections within a box are counted (a divisor of eight) are multiplied by the number of locations for the box. If the box is not square, the corresponding transposed figures and box locations are multiplied and added to the total.

$\endgroup$
6
  • $\begingroup$ Thank you very much for being so patient and explaining such useful concepts. I honestly didn't know what degree is. and it is a good way to differentiate p-long graphs. I can also share what i did last night. i thought total number is almost directly proportional to n, because if we have 2n points, p-long subgraphs will double + their intersections (which is small compared to). I also thought that is we have one p-1 long subgraphs, because we have t connections from every point, but we used some of t to form p-1 long graph. then we have (p-1)*(t-a) number of p-long subgraphs. $\endgroup$ – xcvbnm Apr 17 '15 at 11:34
  • $\begingroup$ this a will be smaller when p goes larger. and in turn, average number of p long subgraphs is about (p-1)!*(t-a)^p . and this number is roughly proportional to n. this is a very very rough estimate but i think i am in the good track $\endgroup$ – xcvbnm Apr 17 '15 at 11:39
  • $\begingroup$ How about the property of being connected? Did you want to include the disconnected $p$-point, $t$-edge subgraphs in your count? $\endgroup$ – hardmath Apr 17 '15 at 14:07
  • $\begingroup$ No, i dont want disconnected subgraphs. But i think this approach may lead to answer, at least for average case where every point has equal number of edges. We can start from 2-point 1 edge line, and calculate number of 2-edge lines or a triangle., and add one edge to existing shape until p. Calculating number of different p-edge graphs according to existing probability of different (p-1)-edge graphs isnt hard, i assume. We just have to be very careful. But after thinking i found that loops are hard, very hard : ) extra attention needed to write an algorithm that wont count them more than once $\endgroup$ – xcvbnm Apr 17 '15 at 21:18
  • $\begingroup$ We can simply drop the disconnected cases from the counts. When every vertex in a graph has the same degree, we say the graph is regular. Note that the chess board has many vertices of degree $4$, but vertices on the boundary of the board have degree $2$ or $3$, so these "grid" graphs are not regular. $\endgroup$ – hardmath Apr 17 '15 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.