  Max Independent Set (MIS) is a paradigmatic problem in theoretical computer
science and numerous studies tackle its resolution by exact algorithms with
non-trivial worst-case complexity. The best such complexity is, to our
knowledge, the $O^*(1.1889^n)$ algorithm claimed by J.M. Robson (T.R. 1251-01,
LaBRI, Univ. Bordeaux I, 2001) in his unpublished technical report. We also
quote the $O^*(1.2210^n)$ algorithm by Fomin and al. (in Proc. SODA'06, pages
18-25, 2006), that is the best published result about MIS.
  In this paper we settle MIS in (connected) graphs with "small" average
degree, more precisely with average degree at most 3, 4, 5 and 6. Dealing with
graphs of average degree at most 3, the best bound known is the recent
$O^*(1.0977^n)$ bound by N. Bourgeois and al. in Proc. IWPEC'08, pages 55-65,
2008). Here we improve this result down to $O^*(1.0854^n)$ by proposing finer
and more powerful reduction rules.
  We then propose a generic method showing how improvement of the worst-case
complexity for MIS in graphs of average degree $d$ entails improvement of it in
any graph of average degree greater than $d$ and, based upon it, we tackle MIS
in graphs of average degree 4, 5 and 6.
  For MIS in graphs with average degree 4, we provide an upper complexity bound
of $O^*(1.1571^n)$ that outperforms the best known bound of $O^*(1.1713^n)$ by
R. Beigel (Proc. SODA'99, pages 856-857, 1999).
  For MIS in graphs of average degree at most 5 and 6, we provide bounds of
$O^*(1.1969^n)$ and $O^*(1.2149^n)$, respectively, that improve upon the
corresponding bounds of $O^*(1.2023^n)$ and $O^*(1.2172^n)$ in graphs of
maximum degree 5 and 6 by (Fomin et al., 2006).
