1
$\begingroup$

I have found an alternate algorithmic proof to this question and want to know whether it is correct:

If $S:d_1,d_2,.......,d_p$ is a non-increasing sequence that is graphical , the sequence $S':d_2-1,d_3-1,....,d_{d_1+1}-1,d_{d_1+2},...,d_p$ is graphical.

Proof: Let us take the set of vertices of the graph $G$ which realizes $S$ be $\{v_1,v_2,....,v_p\}$ with $deg (v_i)=d_i$.

Observation:Note that the pattern in $S'$ is such that all terms from $S$ except $d_1$ are there and each of them upto term $d_{d_1+1}$ in S is reduced by $1$ in $S'$.

  1. Let us delete the vertex $v_1$.
  2. Note that each of the vertices to which it was adjacent to, get their degrees reduced by $1$.

Notes:
2.1. Here,we see that if we write the degrees of vertices after $1$,$2$ is true.
2.2.But those adjacent to $v_1$ can be of two groups:

(i):They are vertices in $\{v_2,v_3,...,v_{d_1+1}\}$ (ii):They are vertices in $\{v_{d_1+2},.....,v_p\}$

2.3:Our goal here thus must be to take the vertices in group(i) which have their degrees decreased in step $1$ and make a new graph such that
their old degrees are restored and operate on the vertices in $\{d_2,d_3,...,d_{d_1+1}\}/B$ such that their degree decreases by one.This would give us $S'$ as the degree sequence of $G'$,the new graph so produced.

  1. Suppose (before deletion of $v_1$ for both point 3 and 4) $u$ of them have degrees that are in the set $\{d_{d_1+2},....,d_p\}$. Denote these under the set $A$.

4.Then, $u$ of the elements with degrees in set $\{d_2,...,d_{d_1+1}\}$ are not adjacent to $v_1$(Deduce this from the fact that $deg(v_1)=d_1$). Denote this group of elements in set $B$.
5.We can establish a bijection $f$ between $B$ and $A$ as their cardinality is same.
6.Take $v_i$ with degree $d_i$ in $B$.
7. Take out an adjacency from $v_i$ which is not with the vertex with degree $ f(d_i)-1$(denote as $k$)[As we have now deleted $v_1$,their past degree is reduced here by one]and add that to vertex $k$. This results in increase in degree of $k$ by one and thus, we get the result because we have created the sequence $S'$ with a Graph for it.
8.It is worth noting that $d_i>0$ for all $i<d_i+1$ as if it had not been,then $degv_1\neq d_1$.
9.The casein which $u$ is $0$ is trivial,since then all the adjacent vertices would come from $\{d_2,....,d_{d_1+1}$ and we can immeadiately obtain $S'$

$\endgroup$
1
  • 1
    $\begingroup$ It might be helpful to define what it means for a sequence to be "graphical." I'm guessing it's a sequence that's the degree sequence of some graph? (Edit: oh, you implicitly define it in the first line of the proof.) $\endgroup$ Aug 26 at 18:18
1
$\begingroup$

If you clean up some of the notation (like "$f(d_i)$" -- you probably meant "$\operatorname{deg} f(v_i)$"), clarify what you mean by step 7, and make the induction proof more structured, then it seems like you have an algorithm.

I'm going to write the pseudocode for the algorithm and prove its correctness, since it might be helpful for you to have an example of what "clear" means to me. Writing it up in this way makes it much easier to verify for yourself whether or not it is correct. (I invite you to carefully write it up in your own way, too!)

Input: a non-increasing graphical sequence $d_1,\dots,d_p$.

  1. Let $G$ be a graph whose degree sequence is $d_1,\dots,d_p$, and let $v_1,\dots,v_p$ denote the distinct vertices of $G$ such that for all $i$, $\operatorname{deg}(v_i)=d_i$.

  2. While there exists a $d_1+2\leq j\leq p$ such that $v_1$ is adjacent to $v_j$:

    1. Let $2\leq k\leq d_1+1$ be such that $v_k$ is not adjacent to $v_1$.
    2. Let $2\leq \ell\leq p$ be such that $\ell\neq j$, $\ell\neq k$, and $v_\ell$ is not adjacent to $v_j$.
    3. Remove the edges $(v_1,v_j)$ and $(v_k,v_\ell)$ and add the edges $(v_1,v_k)$ and $(v_j,v_\ell)$.
  3. Output the degree sequence of $G$ after deleting $v_1$.

Claim: the output of this algorithm is $d_2-1,\dots,d_{d_1+1}-1,d_{d_1+2},\dots,d_p$, so therefore this is a graphical sequence.

The proof of this amounts to a number of small lemmas that explain what each step of this algorithm is doing.

Lemma 1. Step 2 preserves the degree sequence of $G$, and step 2.3 is a valid graph operation.

Proof. Only step 2.3 alters the graph. Step 2.3 is a valid operation since $v_1$, $v_i$, $v_j$, $v_k$, and $v_\ell$ are distinct vertices. The edge replacements preserve degrees, so the degree sequence is preserved. $\square$

Lemma 2. Step 2.1 is valid.

Proof. What "valid" means is that there actually exists such a $k$. (Note: using the terminology of the question, the proof is essentially that there is a bijection between $A$ and $B$, and $A$ is nonempty.) Since we have reached step 2.1, we know that $v_1$ is adjacent to a vertex $v_j$, where $v_j$ is drawn from $v_{d_1+2},\dots,v_p$. We know that $v_i$ is adjacent to $d_1$ different vertices, so it cannot be adjacent to all the vertices $v_2,\dots,v_{d_1+1}$. $\square$

Lemma 3. Step 2.2 is valid.

Proof. Since $k<j$, then $d_k\geq d_j$ since the sequence is non-increasing. Letting $N(v)$ denote the neighborhood of a vertex $v$, then we claim that $N(v_k)\setminus N(v_j)$ is nonempty and does not contain $v_1$ -- using this, then we can let $v_\ell$ be an element in this set difference.

  • Case 1. If $d_k>d_j$, then since $N(v_k)$ does not contain $v_1$ and $N(v_j)$ does, it follows that $N(v_k)\setminus N(v_j)$ contains at least two elements, neither of which are $v_1$, and one of which is not $v_j$.
  • Case 2. Otherwise, consider $d_k=d_j$. For sake of contradiction, suppose there were no such $v_\ell$. Then $N(v_k)\setminus N(v_j)=\{v_j\}$. But this implies that $N(v_j)=(N(v_k)\setminus\{v_j\})\cup \{v_1,v_k\}$, and thus $d_j=d_k+1$, which contradicts $d_k=d_j$.

This completes the lemma. $\square$

Lemma 4. The loop in step 2 eventually terminates.

Proof. Step 2.3 reduces the number of vertices in $v_{d_1+2},\dots,v_p$ that $v_1$ is adjacent to by $1$. Therefore, the loop has at most $p-d_1-1$ iterations. $\square$

Proof of claim. By Lemmas 1-4, the algorithm will run and terminate without errors, and since the output of the algorithm is the degree sequence of a graph, it certainly outputs a graphical sequence. To get to step 3, the condition for the loop in step 2 is false, so $v_1$ is not adjacent to any vertex in $v_{d_1+2},\dots,v_p$. By the observation in the proof of Lemma 2, this means $v_1$ is adjacent to each of the vertices $v_2,\dots,v_{d_1+1}$. Therefore, after deleting $v_1$ the degree sequence is as claimed. $\square$

$\endgroup$
5
  • $\begingroup$ Is $v_l$ defined such that it is adjacent to $v_l$ but not to $v_j$? $\endgroup$
    – user953078
    Aug 27 at 2:34
  • $\begingroup$ I could only deduce that $N(v_k)/N(v_j)$ must have at least one element.How to find the existence of other?) $\endgroup$
    – user953078
    Aug 27 at 2:59
  • $\begingroup$ Can you elaborate Case 2 about $N(v_k)/v(_j)=\{v_j\}?$ I am a bit slow. It just took half an hour for me to fully read it. $\endgroup$
    – user953078
    Aug 27 at 3:12
  • $\begingroup$ I will edit my proof after five to six hours.It still needs some improvements. $\endgroup$
    – user953078
    Aug 27 at 3:42
  • $\begingroup$ @queen_of_fat_blobs Something I should say is that I'm only sure that what I wrote convinces me, and I think I'd find Lemma 3 to be hard to follow if I hadn't written it myself (and didn't have some of the scribbled diagrams on the scrap paper in front of me!) One thing I noticed that might help is that it's easier to deal with a modification of the algorithm where you consider two cases: whether or not $d_j=d_k$. If they're equal, you can swap vertices $v_j$ and $v_k$. If they're not, you proceed to step 2.2. Then it's easier to argue there's a $v_\ell$ with the desired properties. $\endgroup$ Aug 27 at 5:36

Your Answer

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