Sachverhalt: A. A.a. Am 25. Februar 2005 schloss die Stadt U._ mit dem Verein Kinderkrippe X._ einen Mietvertrag bezüglich der Liegenschaft an der V._strasse 16 zur Nutzung als Kinderkrippe ab. Als Kündigungsfrist wurden zwölf Monate jeweils per Ende Dezember vereinbart. Im Jahr 2008 beschloss der Gemeinderat von U._ eine Erweiterung des Angebots vorschulischer familienergänzender Betreuung in der Stadt U._. Diese Aufgabe sollte weiterhin primär von privaten Trägerschaften erbracht werden, subsidiär sollte aber die Stadt U._ selbst geeignete Einrichtungen für den Vorschulbereich aufbauen können. Hierfür wurde das Gesetz vom 27. September 1998 über die familienergänzende Kinderbetreuung in der Stadt U._ dahingehend angepasst, dass die Stadt "bei nachgewiesenem Bedarf... eigene Einrichtungen erstellen und betreiben [kann]" (Art. 3 Abs. 2 kommunalen Gesetz über die familienergänzende Kinderbetreuung; RBC 311). Im Februar 2009 schlossen der Verein Kinderkrippe X._ und die Stadt U._ eine Leistungsvereinbarung des Inhalts ab, dass die Kinderkrippe ihr Angebot um 18 Plätze ausbaut. Damit einhergehend baute die Stadt U._ die Liegenschaft aus und sanierte sie. Zu jenem Zeitpunkt fehlten in der Stadt U._ ca. 20-25 Betreuungsplätze. A.b. Die Parteien waren sich einig, dass mit der Erweiterung betriebliche und wirtschaftliche Risiken verbunden seien, die gemäss dem Ingress der Leistungsvereinbarung durch die Stadt U._ zu tragen seien. Entsprechend wurde vereinbart, dass die Kinderkrippe für zwei neu aufzunehmende Gruppen eine von der bestehenden Gruppe getrennte Kostenstellenrechnung mit einer Übernahmepflicht des Negativsaldos durch die Stadt U._ erstellen würde (Ziff. 4 Abs. 3 lit. a Leistungsvereinbarung). Zudem verpflichtete sich die Stadt U._, in den Jahren 2010-2014 einen sog. Sockelbeitrag von jeweils maximal Fr. 30'000.-- zu leisten, von dem aber ein allfälliger Gewinn der entsprechenden Jahresrechnung bis auf Fr. 5'000.-- in Abzug zu bringen wäre (Ziff. 4 Abs. 3 lit. b der Leistungsvereinbarung). Unter dem Titel "Schlussbestimmungen" wurde die Kündbarkeit der Leistungsvereinbarung jeweils auf Ende des Kalenderjahrs mit einer Kündigungsfrist von zwölf Monaten vereinbart, erstmals per Ende 2014. Bei einer allfälligen Neugestaltung des Finanzausgleichs verpflichteten sich zudem beide Parteien, die Leistungsvereinbarung innert sechs Monaten den neuen Gegebenheiten anzupassen. Schliesslich wurde vereinbart, dass bei Neuabschluss einer Vereinbarung die Parteien die in Ziff. 4 Abs. 3 der gültigen Leistungsvereinbarung festgehaltene Risikoverteilung zwischen Kinderkrippe und Stadt beachteten, unter Hinweis auf die von der Stadt U._ gewünschte Erweiterung der Krippe um zwei Gruppen. Im Rahmen der Leistungsvereinbarung wurde auch eine Anpassung des bestehenden Mietvertrags beschlossen, wonach der jährliche Mietzins nach Umbau, Erweiterung und Sanierung der Liegenschaft V._strasse 16 von bisher Fr. 46'200.-- auf neu Fr. 96'400.-- angepasst wurde (Leistungsvereinbarung Anhang S. 2 f.). Gestützt auf die neu geschaffene gesetzliche Grundlage im kommunalen Gesetz über die familienergänzende Kinderbetreuung (vgl. Sachverhalt lit. A.a) beschloss der Gemeinderat der Stadt U._ die Genehmigung der Erweiterung und Sanierung der Kinderkrippe X._ und sprach hierfür einen Kredit von Fr. 1'147'000.--. A.c. Mit Schreiben vom 9. Juni 2010 zeigte die Stadt U._ dem Verein Kinderkrippe X._ in Anbetracht der tatsächlich entstandenen Sanierungskosten eine Mietzinserhöhung per 1. Januar 2011 auf neu Fr. 108'297.-- an. Die Mietzinserhöhung stützte sich auf die Leistungsvereinbarung (Anpassung nach Vorliegen der definitiven Bauabrechnung der Erneuerungs- und Erweiterungsarbeiten) sowie auf den von der kantonalen Schätzungskommission ermittelten Gebäudemietwert. Am 28. November 2013 liess die Stadt U._ dem Verein Kinderkrippe X._ eine abgeänderte Leistungsvereinbarung zukommen. Gleichzeitig wurde darauf hingewiesen, dass ein vorbereiteter Stadtratsbeschluss vorliege zur Kündigung der bestehenden Leistungsvereinbarung, der allerdings noch zurückbehalten werde, um den Folgevertrag abzuwarten. Sollte keine Vertragsänderung im dargelegten Sinne erfolgen, würde die bestehende Leistungsvereinbarung mittels Stadtratsbeschluss am 17. Dezember 2013 gekündigt. Die abgeänderte Leistungsvereinbarung sah eine finanzielle Unterstützung der Kinderkrippe nur noch im Rahmen der obligatorischen gesetzlichen Vorgaben vor, unter Streichung der Defizitgarantie für die Krippenerweiterung und des zusätzlichen gewinn- und verlustabhängigen Sockelbetrags. A.d. Mit Schreiben vom 9. Dezember 2013 beschwerte sich der Verein Kinderkrippe X._ bei der Stadt U._ über das Vorgehen. Er wies darauf hin, dass die Erweiterung der Liegenschaft mit einhergehender Mietzinserhöhung einzig dem Wunsch der Stadt U._ entsprach. Er selbst habe diesem Wunsch nur bei gleichzeitiger Beteiligung der Stadt U._ an den dadurch entstehenden höheren Kosten (u.a. Mietzins) entsprechen können. Die Stadt U._ stehe somit weiterhin in der Pflicht, einen Beitrag gemäss der vereinbarten Risikoverteilung zu übernehmen, andernfalls eine Teilkündigung für die beiden oberen, neu ausgebauten Stockwerke und die Schliessung der im Jahr 2009 geschaffenen zusätzlichen zwei Gruppen in Frage käme. Dies sei aber, da der Betreuungsbedarf unverändert hoch sei, nicht erstrebenswert. Im Sinne eines Kompromisses bot der Verein Kinderkrippe X._ an, das zusätzlich geschaffene Raumangebot unter Weiterführung sämtlicher Betreuungsplätze für einen reduzierten Mietzinsaufschlag weiterzuführen. Nach seinen Berechnungen würde das Grundangebot, so wie es bis 2009 geführt wurde, heute einen jährlichen Mietzins von Fr. 55'000.-- ausmachen. Von den restlichen Fr. 53'296.-- jährlicher Mietzins, welcher auf das neue Angebot entfallen würde, wäre der Verein bereit, jährlich Fr. 22'700.-- zu übernehmen, was einen neuen Mietzins von Fr. 77'700.-- pro Jahr ergeben würde. Einem solchen Mietzins könnte er ab dem 1. Januar 2015 für die Dauer von zehn Jahren mit einer Option für weitere fünf Jahre zustimmen. A.e. Die Stadt U._ reagierte darauf mit der Kündigung der Leistungsvereinbarung vom 18./26. Februar 2009 per 31. Dezember 2014 (Beschluss des Stadtrats von U._ vom 17. Dezember 2013). B. Am 3. Februar 2014 erhob der Verein Kinderkrippe X._ Beschwerde beim Verwaltungsgericht des Kantons Graubünden mit dem Antrag, der Beschluss des Stadtrats vom 17. Dezember 2013 sei aufzuheben. Eventualiter erhob er Klage auf Verpflichtung der Stadt U._, mit ihm eine neue, konkret ausformulierte Leistungsvereinbarung abzuschliessen. Am 30. April 2015 hiess das Verwaltungsgericht die Beschwerde in der Sache gut und hob den angefochtenen Beschluss des Stadtrats auf. C. Mit Beschwerde vom 5. August 2015 beantragt die Stadt U._ dem Bundesgericht, das Urteil des Verwaltungsgerichts vom 30. April/ 19. Juni 2015 aufzuheben. Es sei festzustellen, dass die Leistungsvereinbarung vom 18./26. Februar 2009 mit Beschluss des Stadtrates vom 17. Dezember 2013 rechtsgültig auf den 31. Dezember 2014 gekündigt worden sei. Eventuell sei die Rechtssache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Der Verein Kinderkrippe X._ beantragt, die Beschwerde sei abzuweisen. Das Verwaltungsgericht des Kantons Graubünden beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei.