Sachverhalt:
A.
A._ ist senegalesischer Staatsangehöriger. Infolge Heirat mit einer schweizerischen Staatsangehörigen wurde ihm im Januar 2003 eine erste Aufenthaltsbewilligung und, nach erfolgter Trennung und einer zweiten Heirat, im Dezember 2006 erneut eine Aufenthaltsbewilligung erteilt. Aus der zweiten Ehe ging ein gemeinsamer Sohn hervor. Im Jahr 2010 trennte sich das Ehepaar, worauf das Migrationsamt des Kantons Solothurn A._ im Juli 2015 aus der Schweiz wegwies. Ein gegen diese Wegweisung geführtes Rechtsmittelverfahren blieb erfolglos. Das kantonale Migrationsamt setzte A._ im November 2015 eine weitere Frist zur Ausreise bis Ende Dezember 2015 an. Kurz vor Ablauf dieser Frist hielt sich A._ in einer psychiatrischen Klinik auf und tauchte anschliessend unter. Am 22. Januar 2016 meldete er sich beim kantonalen Migrationsamt und wurde in Ausschaffungshaft versetzt; seine Hafterstehungsfähigkeit wurde gutachterlich bestätigt.
B.
Mit Entscheid vom 29. März 2016 wies das Verwaltungsgericht des Kantons Solothurn eine Beschwerde von A._ gegen die Ausschaffungshaft ab. Ein erster Vollzug der Ausschaffung scheiterte am 6. April 2016 am Widerstand von A._. Mit Verfügung vom 20. April 2016 ordnete das kantonale Migrationsamt die Verlängerung der Ausschaffungshaft für sechs Monate an. Vom 21. bis 22. April 2016 verbüsste A._ eine eintägige Ersatzfreiheitsstrafe. Mit Entscheid vom 22. April 2016 genehmigte das Haftgericht die Verlängerung der Ausschaffungshaft vom 22. April 2016 bis 21. Oktober 2016. Die dagegen von A._ ohne Anwalt geführte Beschwerde wie auch sein Gesuch um unentgeltliche Rechtsverbeiständung wurden vom kantonalen Verwaltungsgericht mit Urteil vom 17. Mai 2016 abgewiesen.
Mit als Beschwerde bezeichneter Eingabe vom 6. Juni 2016 wendet sich der damals nicht anwaltlich vertretene A._ gegen die "Entscheidungen des kantonalen Haftgerichts bzw. des kantonalen Verwaltungsgerichts vom März 2016, vom 17. Mai 2016 und vom 27. Januar 2016". Er macht sinngemäss geltend, die Anordnungen zu seiner Versetzung in Ausschaffungshaft und deren Verlängerung seien ohne anwaltliche Vertretung und damit in Missachtung seiner Grundrechte erfolgt.
Die Vorinstanz, das kantonale Migrationsamt und das Staatssekretariat für Migration (SEM) schliessen auf kostenfällige Beschwerdeabweisung, soweit darauf eingetreten werden könne. In zwei weiteren eingereichten Stellungnahmen vom 20. Juni 2016 und vom 23. Juni 2016 lässt sich der Beschwerdeführer zur Sache vernehmen. In einer Eingabe vom 24. Juni 2016 ersucht die am 24. Juni 2016 mandatierte Rechtsvertreterin des Beschwerdeführers um Akteneinsicht und Verlängerung der Vernehmlassungsfrist. Mit dem vorliegenden Urteil wird dieses Gesuch gegenstandslos.

Erwägungen:
1.
Gegen letztinstanzliche kantonale richterliche Entscheide betreffend Zwangsmassnahmen im Ausländerrecht und damit verbundene Verfügungen betreffend die Verbeiständung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig (Art. 82 lit. a, Art. 86 Abs. 1 lit. d BGG), weshalb die Eingabe des Beschwerdeführers vom 6. Juni 2016 als solche entgegen genommen werden kann, soweit sie sich gegen das Urteil der Vorinstanz vom 17. Mai 2016 richtet. Auf die frist- und formgerechte (Art. 100 Abs. 1, Art. 42 BGG) Beschwerde des Beschwerdeführers, welcher am vorinstanzlichen Verfahren teilgenommen hat und mit seinen Anträgen unterlegen ist (<ref-law>), ist in diesem Umfang einzutreten.
2.
Dass die gesetzlichen Haftvoraussetzungen grundsätzlich erfüllt sind (Art. 76 Abs. 1 lit. b Ziff. 3 und 4 AuG) und die maximale Haftdauer von 18 Monaten noch nicht erreicht ist (Art. 79 Abs. 1 und 2 lit. b AuG), wird in der vom Beschwerdeführer selbst verfassten Beschwerdeschrift nicht in Frage gestellt. Gegenstand des vorliegenden Verfahrens, welcher sich nach dem angefochtenen Urteil und den Beschwerdeanträgen richtet (vgl. <ref-ruling> E. 4 S. 91), ist nur die unentgeltliche Vertretung des Beschwerdeführers. Nicht weiter einzugehen ist auf die Rüge hinsichtlich der Verlängerung der Ausschaffungshaft wegen Unzumutbarkeit des Vollzugs auf Grund von Krankheit, wurde doch eine Verletzung von Art. 3 EMRK nicht in einer den Anforderungen der qualifizierten Rügepflicht (Art. 106 Abs. 2 BG) genügenden Weise geltend gemacht und können im bundesgerichtlichen Verfahren grundsätzlich keine neuen Beweismittel mehr entgegengenommen werden (<ref-law>).
2.1. Während sich der Anspruch einer bedürftigen Partei auf unentgeltliche Verbeiständung ausschliesslich aus <ref-law> ableitet und somit von der Voraussetzung fehlender Aussichtslosigkeit des Rechtsmittels abhängt, besteht im Bereich des Freiheitsentzugs Anspruch auf eine wirksame Geltendmachung der Rechte. Nach <ref-law> muss jede Person, welcher die Freiheit entzogen ist, die Möglichkeit haben, ihre Rechte in einer den Umständen angemessenen, wirksamen Weise geltend zu machen, weshalb das Erfordernis der fehlenden Aussichtslosigkeit bei einem Freiheitsentzug von einer gewissen Intensität bzw. Dauer sachgerecht zu relativieren und differenziert zu handhaben ist (<ref-ruling> E. 3.2.3 S. 100; Urteil 2C_906/2008 vom 28. April 2009 E. 2.2.2). Während bei der ersten Haftprüfung (Art. 80 Abs. 2 AuG), besondere tatsächliche oder rechtliche Schwierigkeiten vorbehalten, an sich noch nicht durchwegs eine Verbeiständung geboten ist, droht dem Ausländer bei einer Inhaftierung von einer Dauer von über drei Monateneine schwere Freiheitsbeschränkung, die ihn ohne anwaltliche Hilfe vor nicht mehr lösbare Schwierigkeiten tatsächlicher oder rechtlicher Art stellt (<ref-ruling> E. 3.3.1 S. 214; <ref-ruling> E. 3.2.3 S. 100; Urteile 2C_112/2016 vom 19. Februar 2016 E. 2.2.1; 2C_906/2008 vom 28. April 2009 E. 2.2.2); massgeblich für die Verbeiständung ist somit der Zeitpunkt, in welchem diese Dauer erreicht ist. Zur Wahrung ihrer Rechte ist einer ausländischen Person somit bei einer erstmaligen Haftanordnung, die eine Dauer von drei Monaten übersteigt (vgl. Art. 75 Abs. 1 AuG [Ausschaffungshaft]), bereits bei der ersten Haftprüfung (Art. 80 Abs. 2 AuG) bzw. bei einer erstmaligen Haftanordnung von geringerer Dauer im Falle einer diesem Zeitraum gleichkommenden Verlängerung der Haft (vgl. Art. 78 Abs. 2 AuG [Durchsetzungshaft]; zur Höchstdauer Art. 79 Abs. 1 AuG) entweder anlässlich der Haftprüfung oder anlässlich eines Haftentlassungsgesuches (Art. 80 Abs. 5 AuG; zur Identität des diesbezüglichen Prüfprogramms <ref-ruling> E. 2.3.1 S. 412) eine Rechtsvertretung beizugeben.
2.2. Der Beschwerdeführer befand sich im Zeitpunkt der richterlichen Genehmigung der Haftverlängerung durch den Haftrichter am 22. April 2016 seit drei Monaten in Ausschaffungshaft, weshalb eine Verbeiständung im Verfahren vor dem Haftrichter oder zumindest im vorinstanzlichen Beschwerdeverfahren geboten war. Vor diesem Hintergrund durfte die Vorinstanz eine Verletzung des verfassungsmässigen Anspruches auf eine wirksame Durchsetzung der Rechte bei Freiheitsentzug (<ref-law>) nicht mit dem Hinweis darauf verneinen, der Beschwerdeführer sei auf die Möglichkeit einer Rechtsvertretung und auf das solothurnische Anwaltsverzeichnis hingewiesen worden (Urteil 2C_112/2016 vom 19. Februar 2016 E. 2.2.2), und sein im vorinstanzlichen Verfahren gestelltes Gesuch um unentgeltliche Verbeiständung wegen Aussichtslosigkeit des Rechtsmittels abweisen.
3.
Die Beschwerde erweist sich als begründet, weshalb das angefochtene Urteil aufzuheben ist. Die Verletzung des Anspruches auf Verbeiständung bei Freiheitsentzug rechtfertigt es jedoch nicht, den Beschwerdeführer umgehend aus der Haft zu entlassen (<ref-ruling> E. 2c S. 109, letztmals bestätigt in Urteil 2C_112/2016 vom 19. Februar 2016 E. 3.1). Hingegen hat die Vorinstanz dem Beschwerdeführer einen unentgeltlichen Rechtsbeistand - falls möglich in der Person von Rechtsanwältin Clivia Wullimann - zu bestellen und die Streitsache, unter Berücksichtigung einer allfälligen Beschwerdeergänzung, neu zu beurteilen. Die Streitsache wird in diesem Sinne zu einer Fortführung des Verfahrens an die Vorinstanz zurückgewiesen. Bei diesem Verfahrensausgang sind keine Gerichtskosten zu erheben (<ref-law>) und mangels eines Anfalls von Vertretungskosten für die Beschwerde vom 6. Juni 2016 auch keine Parteientschädigung zuzusprechen (Art. 68 Abs. 1 e contrario BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist, und das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 17. Mai 2016 wird aufgehoben. Die Sache wird zur Fortführung des Verfahrens und zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 30. Juni 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Die Gerichtsschreiberin: Mayhall