Question

Question in graph theory:

1. Let (a₁,a₂,a₃,...a_n) be a sequence of integers.

Given that the sum of all integers = 2(n-1)

Write an algorithm that, starting with a sequence (a₁,a₂,a₃,...a_n) of positive
integers, either constructs a tree with this degree sequence or concludes that
none is possible.

Answer 1

We know that every finite tees has at least one leaf,that is a vertex v with degree 1.

A tree with n vertices has exactly n-1 edges

For n=1,this is trivial.

let n-1 holds the condition.

Let T be a tree with n vertices ,

Let v be a leaf of T and e be a unique edge containing v.

So graph T' obtained by deleting v and e from T remains connected and has no cycles as T does not have any.

So T' is also a tree.

Now by inductive hypothesis , T' has (n-1)-1=n-2 edges.

since T' contain all edges of T except e

so T has n-1 edges.

for n=2 ,sum is 2(2-1)=2

so a1+a2=2 , this will be for a1=1 and a2=1

so there is a tree with degree sequence of single edge containing two vertices.

now let ,and let a1,a2,...an be sequence of positive integer such that

here we claim that a_j=1 for some j.

Else,positive integer a_i is greater than 2,so we get

this is a contradiction.

let j=1 so a₁=1 .

similarly, a_k2 for some 2.

else,

so n=2 ,contradicting

so now let

by induction hypothesis there exists a tree whose degree sequence is the sequence of positive integers

attaching one edge to the vertex with degree a₂-1 , we get a tree with degree sequence 1,a₂,a₃,....,a_n .

Please give thumbs up,if you like.