Faits: A. A.a D._ et ses deux enfants, nés en ... et ..., ont bénéficié de l'aide sociale depuis le 1er septembre 2002. En mai 2003, elle s'est mise en ménage commun avec G._, alors marié et dont elle a eu un enfant né en .... Par lettre du 10 août 2004, l'Office social de la Ville de Neuchâtel a informé les intéressés qu'ils seraient considérés sous l'angle de l'aide sociale comme un couple marié. Dès le mois de septembre 2004 G._ s'est constitué un domicile séparé de celui de sa compagne. Au regard de cette nouvelle situation, D._, ainsi que ses enfants, ont pu continuer à bénéficier d'une aide sociale. Au mois de mars 2006, G._ a perdu son poste de travail de gendarme et il s'est inscrit au chômage dès le mois d'avril 2006. A partir du mois de mai 2006, il a repris la vie commune avec D._. Le 15 août 2006, le Tribunal civil du district de La Chaux-de-Fonds a prononcé le divorce des époux G._ et C._ née B._. Il a condamné G._ à verser à l'épouse une contribution mensuelle d'entretien de 1'200 fr. jusqu'au 31 décembre 2018, puis de 700 fr. après cette échéance. L'office cantonal de recouvrement et d'avances des contributions d'entretien a demandé à la caisse de chômage de prélever l'équivalent de la contribution d'entretien de 1'200 fr. sur les indemnités de chômage dues à l'intéressé et de les verser sur le compte dudit office. G._ est par ailleurs astreint à une contribution d'entretien en faveur d'un enfant né d'un précédent mariage. A.b Par décision du 11 octobre 2006, l'Office de l'aide sociale de la Ville de Neuchâtel a notifié à D._ et à G._ qu'il supprimerait l'aide allouée dès le 1er août 2006, motif pris qu'ils vivaient en concubinage avec un enfant commun et qu'ils devaient en conséquence être considérés comme un couple marié sous l'angle de l'aide sociale. Leurs revenus cumulés étaient supérieurs au budget d'aide sociale arrêté à 4'286 fr. Il ne pouvait pas être tenu compte des contributions d'entretien versées par G._. B. D._ et G._ ont recouru contre cette décision. Selon eux, bien qu'ils vécussent en concubinage, seule D._ restait à partir du mois d'août 2006 demanderesse et bénéficiaire de l'aide allouée, à l'exclusion de son partenaire. Celui-ci ne devait donc pas participer à toutes les charges de sa compagne et il convenait, dans la détermination des besoins du couple, de tenir compte des pensions alimentaires versées par G._, ainsi que de sa charge fiscale et d'un prêt qu'il devait rembourser. Le Département de la santé et des affaires sociales (DSAS) du canton de Neuchâtel a rejeté le recours par décision du 12 août 2008. C. Statuant le 31 mars 2009, le Tribunal administratif du canton de Neuchâtel a rejeté un recours formé contre cette décision par D._ et G._. D. D._ et G._ interjettent un recours en matière de droit public dans lequel ils concluent à l'annulation du jugement cantonal, assortie du renvoi de la cause à l'autorité intimée pour nouvelle décision. Ils demandent l'assistance judiciaire pour la procédure fédérale. L'Office de la santé et des affaires sociales de la Ville de Neuchâtel a renoncé à se déterminer. Le DSAS a conclu au rejet du recours. 