2
$\begingroup$

Suppose we have an undirected graph $G=(V,E)$ with $n$ vertices and with max degree of $d>0$.

I need to prove that number of connected subgraphs of $G$ with at most $n\geq k>0$ vertices is $M\leq n\cdot d^{2k}$

My approach was by induction.

For $k=1$ it is true

Suppose we want to prove it for $k=n$ .

let's take any vertice $v\in V$ and run $DFS(v)$ So we will get at most $ d\cdot d^{k-1} \le d^k$ connected commponents.

And because we can take any $ v \in V$ we get that the number of connected subgraphs of $G$ with at most $ k>0$ vertices is $n\cdot d^{k}< n\cdot d^{2k}$

Now my question is: Am I right with my approach? Is there any other solution for this problem?

I really didn't understand why they gave me this upper bound...

$\endgroup$
  • $\begingroup$ I mean connected subgraphs that is subset of the vertices and the edges between them which makes a connected graph of size $k$ $\endgroup$ – ms_stud Jan 27 '18 at 8:36
  • $\begingroup$ I tried to think about this one but the problem is that d can be much smaller than k ( $d<k$ ) $\endgroup$ – ms_stud Jan 27 '18 at 9:50
3
$\begingroup$

Your argument doesn't really constitute a proof, so it is hard to evaluate it. It's not really clear where the maximum degree comes in. You write the inequality $d \cdot d^{k-1} \leq d^k$, but it isn't clear why we're multiply $d$ by $d^{k-1}$. It's not clear why DFS is relevant here (and why you mention connected components when you're interested in connected sub graphs), and it's not clear how you use the inductive hypothesis.

Here is a different argument which hopefully functions better as a proof. Before we can start the proof, we need to understand what we are trying to prove.

Definition. Let $G = (V,E)$ be a graph. An induced subgraph of $G$ is a graph of the form $(U, E \cap U \times U)$ for any non-empty $U \subseteq V$. A connected subgraph of $G$ is an induced subgraph of $G$ which is a connected graph.

Instead of connecting connected subgraphs directly, it is better to count trees instead. We can do this because every connected graph has a spanning tree. This is embodied in the following lemma.

Lemma 1. Let $G$ be a graph on $n$ vertices, and let $1 \leq k \leq n$. The number of connected subgraphs of $G$ having $k$ vertices is at most the number of trees of $k$ vertices contained in $G$. (A tree is contained in $G$ if all the edges of the tree are edges of $G$.)

Proof. Let $C_k$ be the set of connected subgraphs of $G$ having $k$ vertices, and let $T_k$ be the set of trees of $k$ vertices contained in $G$. Since each connected graph has a spanning tree, we can identify a tree of $k$ vertices inside each subgraph in $C_k$. This gives an injective function $f\colon C_k \to T_k$: if $f(c) = t$ and $t$ is a tree on the vertex set $U$, then $c$ is the subgraph induced by $U$. Therefore $|C_k| \leq |T_k|$. $\quad \square$

We can estimate the number of trees of size $k$ contained in $G$ using an appropriate encoding scheme. The basic idea is to pick a starting vertex inside the tree, describe the vertices adjacent to it in the tree, and so on. Each time we describe the adjacent vertices, we can use the fact that every vertex has at most $d$ neighbors.

Lemma 2. Let $G$ be a graph on $n$ vertices of maximum degree $d$. The number of trees of $k$ vertices contained in $G$ is at most $nd^{2k-2}$.

Proof. The lemma clearly holds for $k=1$, so suppose that $k \geq 2$. Fix an arbitrary ordering on the vertices of $G$. We describe a procedure that receives as input a tree $T$ and a leaf $v$, and outputs a succinct numerical encoding of $T$. The procedure, Encode, uses a subroutine, Encode-child, which accepts $T$, a vertex $u \in T$, and another vertex $p$ which is adjacent to $u$ in the tree $T$.

Encode(T, v):
  Let u be the unique neighbor of v in T.
  Suppose that u is the i'th smallest neighbor of v in G.
  Output v, i, and run Encode-child(T, u, v).

Encode-child(T, u, p):
  Let u_1, ..., u_m be the neighbors of u in T other than p.
  Output the degree of u in T, i.e., m+1.
  For i = 1, ..., m:
    Suppose that u_i is the j'th smallest neighbor of u in G.
    Output j, and run Encode-child(T, u_i, u).

(We assume that $i$ in Encode and $j$ in Encode-child run from $1$ to $d$.)

What does the output look like? The first item in the sequence is a vertex, which we can identify as a number from $1$ to $n$ (using the order of the vertices of $G$). All other items are numbers from $1$ to $d$. Thinking of $T$ as rooted at the starting leaf $v$, for each non-root vertex we encode both its degree and its index as a child of its parent, for a total of $2(d-1)$ numbers.

We can reconstruct the tree from this encoding. Indeed, it is not difficult to explicitly spell out a decoding procedure which gets as input the sequence of $1+2(d-1)$ numbers, and outputs a tree. It is more challenging to prove that if we encode a tree $T$ and run the decoding procedure, then we get back the tree $T$; however, the challenge is mostly technical rather than conceptual, since intuitively it is clear that the decoding algorithm works. We therefore leave these steps to the curious reader.

We conclude that the encoding procedure described above is an injective mapping from the set of pairs $(T,v)$, where $T$ is a tree of $k$ vertices contained in $G$ and $v$ is a leaf of $T$, to the set of sequences lying in $[n] \times [d]^{2k-2}$ (where $[m] := \{1,\ldots,m\}$). Since every tree contains a leaf, this shows that the number of trees is at most $nd^{2k-2}$ (in fact, since every tree contains at least two leaves, we can improve this to $nd^{2k-2}/2$). $\quad\square$

As a conclusion, we can estimate from above the number of trees having at most $k$ vertices by $$ \sum_{\ell=1}^k nd^{2\ell-2} = \frac{nd^{2k}-n}{d^2-1} \leq nd^{2k}. $$ According to Lemma 1, this is also an upper bound on the number of connected subgraphs having $k$ vertices.

Is this bound tight? Probably not. Our encoding scheme is quite wasteful. For example, when encoding $j$ in Encode-child, we can use a number from $1$ to $d-1$, since we know that $u_i \neq p$. This improves the exponent to $d(d-1)$ from $d^2$.

In order to determine the optimal exponent, we can take as our graph $G$ the infinite $d$-ary tree, and count the number of trees of $k$ vertices rooted at a fixed vertex of $G$. This is worked out in this math.se question, which shows that the optimal exponent is $(d-1)^{d-1}/(d-2)^{d-2}$. For example, when $d=3$ the optimal exponent is $4$ rather than $6$ (the well-known asymptotic of Catalan numbers), and when $d=4$ it is $6.75$ rather than $12$.

$\endgroup$
  • $\begingroup$ Brilliant!!! My approach of using DFS was from an intuition I had of doing a successor operation on a tree but I just couldn't prove it right as you did...Thank you! $\endgroup$ – ms_stud Jan 28 '18 at 21:39

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.