Sachverhalt:
A.
A.a. Der (nord) mazedonische Staatsangehörige A.A._ (geb. 1975) hielt sich im Jahr 1994 zu Erwerbszwecken illegal in der Schweiz auf. Er wurde am 5. Oktober 1994 nach Nordmazedonien ausgeschafft und mit einem zweijährigen Einreiseverbot belegt.
A.b. Am 5. November 2013 heiratete A.A._ die slowakische Staatsangehörige D._ (geb. 1987) in Nordmazedonien. Die Ehefrau reiste am 1. Oktober 2014 in die Schweiz ein, um einer Erwerbstätigkeit nachzugehen. Sie verfügt über eine Aufenthaltsbewilligung EU/EFTA mit Gültigkeit bis am 19. April 2020. A.A._ reiste am 29. Juni 2015 als Tourist in die Schweiz ein und erhielt am 13. Juli 2015 im Rahmen des Familiennachzuges zu seiner Ehegattin eine bis am 12. Juli 2020 gültige Aufenthaltsbewilligung. Aus einer früheren Beziehung hat A.A._ zwei Kinder, eine Tochter namens B.A._ (geb. 2002) und einen Sohn namens C.A._ (geb. 2004). Die beiden Kinder reisten am 25. Mai 2016 als Touristen zu ihrem Vater in die Schweiz ein und erhielten am 22. Juli 2016 im Rahmen des Familiennachzuges zum Vater eine Aufenthaltsbewilligung.
A.c. Die Eheleute A.A._ und D._ wohnen in U._/SG. A.A._ arbeitet seit dem 1. September 2015 in V._/SG als Plattenleger. Im Verlaufe der Abklärungen betreffend das Familiennachzugsgesuch für die beiden Kinder wurde bekannt, dass die Ehefrau seit dem 1. Mai 2016 einer Erwerbstätigkeit in einem 50%-Pensum im Kanton Wallis nachging. Sie arbeitete bei ihrer Schwester im Restaurant E._ in W._/VS und fuhr eigenen Angaben zufolge wegen der grossen Entfernung und der unregelmässigen Arbeitstage nur in der Freizeit nach U._/SG zurück. Diese Erkenntnis veranlasste das Migrationsamt dazu, die örtlich zuständige Polizei mit Schreiben vom 8. Februar 2017 mit einer diskreten Umfeldabklärung zu beauftragen, dies wegen des Verdachts auf das Bestehen einer Scheinehe. Im Bericht vom 2. März 2017 hielt die Polizei hierzu fest, dass der Briefkasten und die Türglocke mit dem Namen der beiden Ehepartner angeschrieben sei. Bei den Kontrollen seien jedoch keine Personen angetroffen worden. In der Folge wurden die Eheleute am 25. April 2017 jeweils einzeln polizeilich befragt. Bei verschiedenen Fragen gaben die Eheleute voneinander abweichende Antworten (namentlich betreffend die Umstände des Kennenlernens, die Trauung, die Beziehung zu den Kindern des Beschwerdeführers, Namen der Schwiegereltern, Konfession etc.).
A.d. Aufgrund der gewonnenen Erkenntnisse und unter Würdigung aller Indizien kam das Migrationsamt mit Schreiben vom 19. Juni 2017 zum Ergebnis, es liege eine Scheinehe vor, die lediglich zur Umgehung der ausländerrechtlichen Vorschriften eingegangen worden sei. Im Rahmen des rechtlichen Gehörs nahm die Rechtsvertreterin von A.A._ mit Schreiben vom 27. Juli 2017 zu den Vorwürfen Stellung und reichte diverse undatierte Fotos der Trauung, von Ferienaufenthalten und aus der Freizeit ein, aufgrund derer der Vorwurf der Scheinehe in Abrede gestellt wurde.
B.
Mit Verfügung vom 4. Januar 2018 widerrief das Migrationsamt die Aufenthaltsbewilligungen von A.A._ und den beiden Kindern und wies alle drei an, die Schweiz innert 60 Tagen nach Rechtskraft der Verfügung zu verlassen. Zur Begründung führte es im Wesentlichen an, es müsse davon ausgegangen werden, dass A.A._ und D._ eine Scheinehe eingegangen seien. Damit sei ein Widerrufsgrund gegeben. Selbst wenn das Vorliegen einer Scheinehe verneint werden müsste, würde sich die Berufung auf die Ehe letztlich als rechtsmissbräuchlich erweisen, weil keine eheliche Gemeinschaft mehr vorliege. Die eheliche Gemeinschaft in der Schweiz habe jedenfalls keine drei Jahre angedauert, weshalb A.A._ - und die im Rahmen des Familiennachzugs eingereisten Kinder - keine Ansprüche auf Beibehaltung der Aufenthaltsbewilligungen geltend machen können. Die Rückkehr in ihr Heimatland sei A.A._ und seinen Kindern zumutbar, zumal er sich erst seit Juni 2015(bzw. die Kinder seit 25. Mai 2016) in der Schweiz aufhalten würden. Den grössten Teil seines Lebens hätten er, wie auch die beiden Kinder, im Heimatland verbracht und sie pflegten mit der dort ansässigen Familie weiterhin intensive Kontakte. Den gegen die abschlägige Verfügung von A.A._ und den beiden Kindern erhobenen Rekurs wies das Sicherheits- und Justizdepartement des Kantons St. Gallen mit Entscheid vom 11. Februar 2019 ab. Am 23. Mai 2019 wies das Verwaltungsgericht des Kantons St. Gallen, Abteilung II, die gegen den Rekursentscheid erhobene Beschwerde ab.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 25. Juni 2019 beantragen A.A._ und seine beiden Kinder die Aufhebung des angefochtenen Urteils. Den Beschwerdeführenden seien die Aufenthaltsbewilligungen zu belassen und es sei von einer Wegweisung abzusehen. Zudem sei der Beschwerde in Bezug auf die mit dem angefochtenen Entscheid verbundenen Ausreiseverpflichtung die aufschiebende Wirkung zu erteilen.
Mit Präsidialverfügung vom 27. Juni 2019 wurde auf das Gesuch um aufschiebende Wirkung nicht eingetreten, da die Ausreiseverpflichtung bis zum Abschluss des bundesgerichtlichen Verfahrens nicht in Rechtskraft erwachsen kann.
Der Abteilungspräsident zog als Instruktionsrichter die kantonalen Akten bei und lud die Vorinstanzen sowie das Staatssekretariat für Migration zur Vernehmlassung ein. Die Vorinstanz sowie das Sicherheits- und Justizdepartement des Kantons St. Gallen beantragen die Abweisung der Beschwerde und verweisen zur Begründung beide auf das Urteil der Vorinstanz. Das Staatssekretariat für Migration hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1.
1.1. Angefochten ist ein letztinstanzlicher kantonaler Entscheid auf dem Gebiet des Ausländerrechts, welcher grundsätzlich der Beschwerde in öffentlich-rechtlichen Angelegenheiten unterliegt (Art. 82 lit. a i.V.m. <ref-law>). Gemäss <ref-law> ist die Beschwerde unzulässig gegen Entscheide betreffend ausländerrechtliche Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. Vorliegend geht es nicht um die Erteilung, sondern um den Widerruf von drei noch laufenden Bewilligungen. In dieser Ausgangslage ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten ohne Weiteres zulässig (<ref-ruling> E. 1.2.1 S. 4; Urteile 2C_292/2019 vom 8. April 2019 E. 2; 2C_96/2012 vom 18. September 2012 E. 1.1).
1.2. Das Bundesgericht prüft das Bundesrecht von Amtes wegen (<ref-law>; <ref-ruling> E. 2.1 S. 231). In Bezug auf die verfassungsmässigen Individualrechte (einschliesslich der Grundrechte) gilt eine qualifizierte Rüge- und Begründungsobliegenheit (<ref-law>; <ref-ruling> E. 5.1 S. 41). Diese qualifizierte Rüge- und Begründungsobliegenheit nach <ref-law> verlangt, dass in der Beschwerde klar und detailliert anhand der Erwägungen des angefochtenen Entscheids dargelegt wird, inwiefern verfassungsmässige Individualrechte verletzt worden sein sollen (vgl. <ref-ruling> E. 1.4 S. 5; <ref-ruling> E. 1.4.2 S. 254).
1.3.
1.3.1. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die vorinstanzlichen Sachverhaltsfeststellungen können von Amtes wegen oder auf Rüge hin berichtigt werden, wenn sie offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen und wenn die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (<ref-law> und <ref-law>; <ref-ruling> E. 5.1 S. 232). "Offensichtlich unrichtig" ist mit "willkürlich" gleichzusetzen (<ref-ruling> E. 2.3.3 S. 42 f.). Die Anfechtung der vorinstanzlichen Feststellungen unterliegt der qualifizierten Rüge- und Begründungsobliegenheit (<ref-ruling> E. 4.1 S. 52 f.; vorne E 1.2). Wird die Beschwerde diesen Anforderungen nicht gerecht, bleibt es beim vorinstanzlichen Sachverhalt (<ref-ruling> E. 1.3.1 S. 18).
1.3.2. Zur Sachverhaltsfeststellung gehört auch die auf Indizien gestützte Beweiswürdigung. Die Sachverhaltsfeststellung bzw. Beweiswürdigung erweist sich als willkürlich im Sinne von <ref-law>, wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat (<ref-ruling> E. 2.3 S. 265 f.; Urteil 2C_310/2014 vom 25. November 2014 E. 2). Dass der vom Gericht festgestellte Sachverhalt nicht mit der Darstellung der beschwerdeführenden Person übereinstimmt, begründet für sich allein hingegen noch keine Willkür (<ref-ruling> E. 6.2.3 S. 273 mit Hinweisen). Zudem ist erforderlich, dass der angefochtene Entscheid nicht nur in der Begründung, sondern auch im Ergebnis willkürlich ist (<ref-ruling> E. 7.1 S. 124; <ref-ruling> E. 3.6.2 S. 287). Eine entsprechende Rüge ist substanziiert vorzubringen; auf rein appellatorische Kritik an der Beweiswürdigung der Vorinstanz geht das Gericht nicht ein (<ref-ruling> E. 2.3 S. 266; <ref-ruling> E. 10.1 S. 444 f.; vorne E. 1.2).
1.3.3. Die Beschwerdeführenden beanstanden den festgestellten Sachverhalt der Vorinstanz insoweit, als dass der Umstand, dass die Ehefrau des Beschwerdeführers vom 1. Mai 2016 bis zum 28. Februar 2018 einer Erwerbstätigkeit in einem 50%-Pensum in W._/VS nachging, nicht bereits im Zusammenhang mit den Abklärungen betreffend dem Familiennachzugsgesuch der Kinder bekannt geworden sei, sondern auf eine schriftliche Mitteilung der Ehefrau vom 27. Juni 2016 zurückgehe. Die Aufenthaltsbewilligungen der Kinder seien somit ungeachtet dieser Mitteilung erteilt worden und der Ermittlungsauftrag des Migrationsamts an die Polizei, betreffend die diskreten Umfeldabklärungen wegen des Verdachts auf eine Scheinehe, sei erst im Februar 2017 erteilt worden.
1.3.4. Diese Sachverhaltsrüge ist unbegründet. Aus den Vorakten des Migrationsamtes (pag. 64 f./356), auf die hier zurückgegriffen werden kann (<ref-law>), geht hervor, dass der Beschwerdeführer den Arbeitsvertrag seiner Ehefrau betreffend ihre Arbeitsstelle in W._/VS dem Familiennachzugsgesuch für seine Kinder beilegte. Zutreffend ist, dass die Ehefrau dem Migrationsamt diesen Umstand mit Schreiben vom 27. Juni 2016 auch noch persönlich mitgeteilt hat. Gestützt auf diese Erkenntnis wurde in der Folge der entsprechende Ermittlungsauftrag an die Polizei wegen des Verdachts auf das Bestehen einer Scheinehe in Auftrag gegeben. Inwieweit die Beschwerdeführenden aus dem Umstand, dass die polizeilichen Ermittlungen erst nach der Erteilung der Aufenthaltsbewilligungen an die Kinder in Auftrag gegeben worden sein sollen, Rechte zu ihren Gunsten ableiten wollen, ist nicht ersichtlich und wird auch nicht näher begründet. Die vorgebrachten Sachverhaltsrügen genügen daher den Anforderungen der qualifizierten Rüge- und Begründungsobliegenheit nicht und sind unbeachtlich. Die Sachverhaltsfeststellungen der Vorinstanz sind deshalb für das Bundesgericht verbindlich (vorne E. 1.3.1).
1.4. Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Das Vorbringen von Tatsachen, die sich erst nach dem angefochtenen Entscheid ereigneten oder entstanden (echte Noven), ist vor Bundesgericht unzulässig (<ref-ruling> E. 1.2 S. 22 f. mit Hinweisen). Der Praktikumsvertrag der Tochter des Beschwerdeführers datiert vom 19. Juni 2019 und ist somit erst nach dem angefochtenen Urteil vom 23. Mai 2019 abgeschlossen worden. Folglich stellt dies ein echtes Novum dar und ist im vorliegenden Verfahren unbeachtlich.
2.
2.1. Der Beschwerdeführer beanstandet eine rechtswidrige Beweis-mittelbeschaffung. Er rügt, dass die polizeilichen Befragungsprotokolle der Eheleute vom 25. April 2017, auf welche sich die Vorinstanz hinsichtlich ihrer Argumentation für die Annahme einer Scheinehe primär abstützt, nicht verwertbar seien. Auf die Eheleute sei anlässlich der Befragungen "Zwang und Druck" ausgeübt worden. Er begründet die Drucksituation damit, dass die Eheleute jeweils eine schriftliche Vorladung als beschuldigte Person erhielten. Sie seien deshalb und aufgrund der Rechtsmittelbelehrung anlässlich der polizeilichen Befragung davon ausgegangen, sie befänden sich in einem Strafverfahren. Dieser Umstand habe bei den Eheleuten starken emotionalen Stress ausgelöst, der zu einer Drucksituation geführt habe. Es ist somit zu prüfen, ob die Vorinstanz verfassungsrechtlich haltbar bzw. bundesrechtskonform auf die vorgenannten Befragungsprotokolle abstellen durfte.
2.2. Zunächst ist festzuhalten, dass im Verwaltungsverfahren der Untersuchungsgrundsatz gilt. Beruft sich eine ausländische Person auf eine Bestimmung des Ausländergesetzes, um daraus einen Aufenthaltsanspruch abzuleiten, obliegt es der zuständigen Behörde, die entsprechenden Voraussetzungen zu prüfen und die hierfür notwendigen Abklärungen zur Feststellung des rechtserheblichen Sachverhalts vorzunehmen. Indessen wird der Untersuchungsgrundsatz durch die Mitwirkungspflicht der Parteien relativiert (<ref-law> [SR 142.20]; bis zum 1. Januar 2019 AuG). Betroffene ausländische Personen wie auch an ausländerrechtlichen Verfahren beteiligte Dritte müssen ausdrücklich an der Feststellung des für die Anwendung des Ausländergesetzes massgebenden Sachverhalts mitwirken, wobei sie insbesondere zutreffende und vollständige Angaben über die für die Regelung des Aufenthalts wesentlichen Tatsachen machen müssen (Urteile 2C_981/2017 vom 18. Februar 2019 E. 3.1; 2C_118/2017 vom 18. August 2017 E. 3.3.). Dem strafprozessualen Schweigerecht kommt dabei nach bundesgerichtlicher Rechtsprechung in aller Regel keine direkte Bedeutung zu (<ref-ruling> E. 3.4.2 S. 70; Urteil 2C_118/2017 vom 18. August 2017 E. 3.3). Zwar hat der Europäische Gerichtshof für Menschenrechte (EGMR) erkannt, es könneein Verstoss gegen das in Art. 6 Ziff. 1 EMRK garantierte Recht auf ein faires Verfahren vorliegen, wenn bei der Sachverhaltsermittlung im Verwaltungsverfahren Zwang oder Druck ausgeübt werde und die auf diesem Wege aufgrund der verwaltungsrechtlichen Mitwirkungspflicht (hier <ref-law>) gewonnenen Informationen im Strafprozess gegen dieselbe Person verwendet werden (vgl. Urteil des EGMR Chambaz gegen die Schweiz vom 5. April 2012 [Nr. 11663/04] § 52). Diese Konstellation hätte eine Verletzung des strafrechtlichen Grundsatz des "nemo tenetur se ipsum accusare" zur Folge, wonach niemand gezwungen werden soll, sich in einem Strafverfahren selbst zu belasten (<ref-ruling> E. 8.2 S. 214). Auf diese Art gewonnene Informationen wären in einem Strafverfahren deshalb nicht verwertbar.
2.3. Im hier zu beurteilenden Fall rügt der Beschwerdeführer jedoch gerade die umgekehrte Situation. Er beanstandet, dass Aussagen aus einem Strafverfahren nicht in einem gegen ihn laufenden Verwaltungsverfahren verwertet werden dürfen. Diese Rüge ist aus mehreren Gründen nicht zu hören. Einerseits kann eine Scheinehe gestützt auf <ref-law> strafrechtliche Sanktionen nach sich ziehen. Dass die Polizei die Eheleute auf ihr strafprozessrechtliches Aussageverweigerungsrecht hingewiesen hat, ist deshalb nicht zu beanstanden. Andererseits ist die gegenseitige Amtshilfe zwischen den beteiligten Behörden gemäss <ref-law> zu beachten, wonach sich die mit dem Vollzug des AIG betrauten Behörden bei der Erfüllung ihrer Aufgaben gegenseitig unterstützen und dabei insbesondere die hierzu notwendigen Daten und Informationen auf Verlangen einer anderen involvierten Behörde herauszugeben haben. Im Ergebnis durfte das Migrationsamt die Polizei deshalb für die Befragung der Eheleute beiziehen und diese durfte die Eheleute ihrerseits auf ihr strafprozessrechtliches Aussageverweigerungsrecht hinweisen. Der Hinweis auf das Aussageverweigerungsrecht führt zudem dazu, dass vorliegend die im Vergleich zum Verwaltungsverfahren höheren strafprozessualen Anforderungen an die Verwertbarkeit von Beweismitteln (vorne E. 2.2) ohne Weiteres erfüllt sind. Die Eheleute haben somit trotz dem Wissen um ihr Aussageverweigerungsrecht freiwillig und aus eigenem Antrieb sämtliche Fragen der Polizei beantwortet. Darüber hinaus ist Art. 6 EMRK in ausländerrechtlichen Verfahren ohnehin nicht anwendbar (<ref-ruling> E. 4. 4. 2 S. 133). Die Befragungsprotokolle der Eheleute vom 25. April 2017 sind deshalb verwertbar.
3.
3.1.
Der Beschwerdeführer ist weiter der Auffassung, die Vorinstanz habe seinen Anspruch auf rechtliches Gehör (<ref-law>; Art. 6 EMRK) verletzt. Er beanstandet, die Vorinstanz habe sämtliche eingereichten Beweismittel (Chat-Nachrichten und Fotos) ignoriert oder als unerheblich abgetan und habe sich zudem nicht mit seinen Argumenten auseinandergesetzt. Insbesondere habe die Vorinstanz seinen Anspruch auf rechtliches Gehör verletzt, indem sie auf die Vorladung von Zeugen aus seinem näheren Umfeld sowie auf eine nochmalige Befragung des Beschwerdeführers und seiner Ehefrau verzichtet habe.
3.2. Hinsichtlich des Anspruchs auf rechtliches Gehör ist festzuhalten, dass der Beschwerdeführer auch diesbezüglich keine Rechte aus Art. 6 EMRK ableiten kann (vorne E. 2.3). Die Frage, ob die Vorinstanz das rechtliche Gehör des Beschwerdeführers verletzt hat, beurteilt sich mangels Rügen zum kantonalen Recht einzig nach <ref-law>.
3.3. Das rechtliche Gehör (<ref-law>) verlangt, dass die Behörde die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt (<ref-ruling> E. 5.2 S. 70). Daraus folgt die Verpflichtung der Behörde, ihren Entscheid zu begründen. Dabei ist es nicht erforderlich, dass sie sich mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Punkte beschränken. Die Begründung muss so abgefasst sein, dass sich der Betroffene über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann. In diesem Sinne müssen wenigstens kurz die Überlegungen genannt werden, von denen sich die Behörde hat leiten lassen und auf die sich ihr Entscheid stützt (<ref-ruling> E. 5.2 S. 70; <ref-ruling> E. 5.1 S. 237).
3.4. Keine Verletzung des rechtlichen Gehörs liegt weiter vor, wenn ein Gericht darauf verzichtet, beantragte Beweise abzunehmen, weil es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 3.1.3 S. 435).
3.5. Dem angefochtenen Urteil kann entnommen werden, dass sich die Vorinstanz zu sämtlichen Beweismitteln äussert und diese auf ihren jeweiligen Beweiswert hin umfassend würdigt. Betreffend die Fotoaufnahmen äussert sich die Vorinstanz dahingehend, dass diesen nur ein geringer Beweiswert zuzumessen sei. Nach den für das Bundesgericht verbindlichen Feststellungen der Vorinstanz (<ref-law>; vorne E. 1.3.1) sind die Bilder mit keinen Daten versehen, obwohl dies bei Digitalkameras und Smartphones heutzutage üblich ist. Auch mit den Chat-Nachrichten setzt sich die Vorinstanz gründlich auseinander und kommt zum Ergebnis, dass diese zwar aufzeigen, dass der Beschwerdeführer mit seiner Ehefrau über die elektronischen Kommunikationsmittel in Kontakt stand, aufgrund der sehr oberflächlich und allgemein gehaltenen Gesprächsinhalte der behauptete Ehewille jedoch nicht belegt werden könne (zum Ganzen E. 4 des angefochtenen Urteils). Vor diesem Hintergrund ist nicht ersichtlich, inwieweit die Vorinstanz die vom Beschwerdeführer eingereichten Beweismittel ignoriert oder welche entscheidrelevanten Informationen sie nicht berücksichtigt haben soll. In diesem Zusammenhang liegt somit keine Verletzung des Anspruchs des Beschwerdeführers auf rechtliches Gehör (<ref-law>) vor.
3.6.
3.6.1. Näher zu prüfen ist die Rüge, die Vorinstanz habe den Anspruch des Beschwerdeführers auf rechtliches Gehör (<ref-law>) verletzt, indem sie auf die von ihm beantragten Zeugenbefragungen der Nachbarn, von Personen aus seinem näheren Umfeld sowie auf eine nochmalige Befragung der Eheleute verzichtete. Diese Rüge ist im Zusammenhang mit den rechtlichen Anforderungen an den Nachweis einer Scheinehe zu beurteilen.
3.6.2. Als Ehegatte einer hier aufenthaltsberechtigten EU-Bürgerin hat der Beschwerdeführer Anspruch auf eine Aufenthaltsbewilligung EU/EFTA (Art. 7 lit. d FZA i.V.m. Art. 3 Anhang I FZA). Die Aufenthaltsbewilligung EU/EFTA steht jedoch unter dem Vorbehalt des Rechtsmissbrauchs (<ref-law>) und kann namentlich beim Vorliegen einer Scheinehe widerrufen werden (<ref-law>; <ref-law> [SR 142.203]; <ref-ruling> E. 2.1 S. 395; <ref-ruling> E. 9 S. 129 ff.; Urteil 2C_1077/2017 vom 8. Januar 2019 E. 4.1).
3.6.3. Eine Scheinehe liegt nicht bereits dann vor, wenn auch ausländerrechtliche Motive den Eheschluss beeinflusst haben. Erforderlich ist vielmehr, dass der Wille zur Führung der Lebensgemeinschaft im Sinne einer auf Dauer angelegten wirtschaftlichen, körperlichen und spirituellen Verbindung zumindest bei einem der Ehepartner fehlt (<ref-ruling> E. 3b S. 102; Urteil 2C_292/2017 vom 8. März 2018 E. 4.2). Dabei ist es grundsätzlich Sache der Migrationsbehörde, die Scheinehe nachzuweisen. Dass eine Scheinehe vorliegt, darf nicht leichthin angenommen werden. Diesbezügliche Indizien müssen klar und konkret sein (<ref-ruling> E. 4.2 S. 10; <ref-ruling> E. 2.2 S. 151; Urteil 2C_118/2017 vom 18. August 2017 E. 4.2). Solche Indizien können äussere Begebenheiten sein wie die Umstände des Kennenlernens, eine kurze Dauer der Bekanntschaft, eine drohende Wegweisung, das Fehlen einer Wohngemeinschaft, ein erheblicher Altersunterschied, Schwierigkeiten in der Kommunikation, fehlende Kenntnisse über den anderen oder die Bezahlung einer Entschädigung für die Heirat. Sie können aber auch innere (psychische) Vorgänge betreffen (BGE <ref-ruling> E. 2.3 S. 152; Urteil 2C_200/2017 vom 14. Juli 2017 E. 3.2). In beiden Fällen handelt es sich um tatsächliche Feststellungen, die das Bundesgericht nur auf offensichtliche Unrichtigkeit oder Rechtsverletzung hin überprüft (<ref-law>; vorne E 1.3.1). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe sei rechtsmissbräuchlich oder bezwecke die Umgehung fremdenpolizeilicher Vorschriften BGE <ref-ruling> E. 2.3 S. 152, Urteil 2C_1049/2018 vom 21. März 2019 E. 2.2).
3.6.4. Der Untersuchungsgrundsatz der Migrationsbehörden wird durch die Mitwirkungspflicht der Parteien relativiert (<ref-law>; vorne E. 2.2). Diese kommt naturgemäss bei Tatsachen zum Tragen, die eine Partei besser kennt als die Behörden und die ohne ihre Mitwirkung gar nicht oder nicht mit vernünftigem Aufwand erhoben werden können (vgl. <ref-ruling> E. 8.6.4 S. 496 f.; Urteile 2C_118/2017 vom 18. August 2017 E. 4.2, 2C_200/2017 vom 14. Juli 2017 E. 3.3). Insbesondere für den Fall, dass bereits bedeutsame Hinweise für eine Ausländerrechtsehe sprechen, wird von den Eheleuten erwartet, dass sie von sich aus Umstände vorbringen und belegen, die den echten Ehewillen glaubhaft machen (Urteile 2C_1077 vom 8. Januar 2019 E. 4.1; 2C_1019/2016 vom 9. Mai 2017 E. 2.3; 2C_868/2015 vom 27. Januar 2016 E. 3.1, 3.5.3). In einer solchen Fallkonstellation obliegt den Betroffenen der Gegenbeweis. Dies korreliert mit der Pflicht der Migrationsbehörden, die ordentlich angebotenen Beweise abzunehmen, sofern diese dazu geeignet sind, das Vorliegen einer ehelichen Gemeinschaft zu belegen (Urteile 2C_379/2018 vom 23. April 2019 E. 2.2). Wenn also die Vorinstanz davon ausgegangen ist, dass die Indizienlage für das Bestehen einer Scheinehe so gewichtig ist, dass dem Beschwerdeführer der Gegenbeweis obliegen würde, können die angebotenen Beweise nicht leichthin abgelehnt werden, da ansonsten die Verfahrensrechte des zur Mitwirkung Verpflichteten ausgehebelt würden (Urteil 2C_1049/2018 vom 21. März 2019 E. 4.2).
3.6.5. Die Wohnsituation der Ehegattin und ihre damit verbundene Ortsabwesenheit ist gemäss der für das Bundesgericht verbindlichen Sachverhaltsfeststellungen der Vorinstanz (vorne E. 1.3.2) das wesentlichste Indiz dafür, dass zwischen den Eheleuten keine eheliche Gemeinschaft bestehe und damit von einer Scheinehe auszugehen sei. Es liegen noch weitere Indizien vor, die auf eine Scheinehe hindeuten (E. 4.4 des angefochtenen Entscheids), allerdings sind diese für sich alleine betrachtet nicht besonders ausgeprägt.
3.6.6. Der von der Vorinstanz ins Feld geführte Altersunterschied von zwölf Jahren ist nicht besonders auffällig; gleiches gilt für die Zeitdauer zwischen dem Kennenlernen und der Heirat, die sich als nicht besonders kurz erweist.
3.6.7. Der Vorinstanz ist insoweit zuzustimmen, als dass sich aus den polizeilichen Befragungsprotokollen durchaus mehrere und teilweise beträchtliche Widersprüche ergeben (E. 4.4 des angefochtenen Entscheids). Diesbezüglich ist aber ebenso zu beachten, dass die Aussagen der Eheleute über weite Strecken auch Übereinstimmungen aufweisen. Zudem ist zu berücksichtigen, dass die Ehe nicht geschlossen wurde, um eine drohende Ausweisung zu umgehen. Die Vorinstanz hat diesbezüglich festgestellt, dass die Hochzeit stattgefunden hat, bevor einer der Ehegatten über ein Aufenthaltsrecht in der Schweiz verfügte. Darüber hinaus ergibt sich aus dem vorinstanzlichen Sachverhalt, dass die eheliche Wohnung in U._/SG während des gesamten Aufenthalts in der Schweiz beibehalten wurde und die Ehegattin in ihrer Freizeit zumindest teilweise nach U._/SG zurückgekehrt ist.
3.6.8. Die Vorinstanz ist aufgrund einer Gesamtwürdigung der vorgenannten Indizien zum Ergebnis gelangt, dass mit überwiegender Wahrscheinlichkeit von einer Scheinehe auszugehen sei.
3.6.9. Aufgrund dieser vorinstanzlichen Schlussfolgerung war es die Aufgabe des Beschwerdeführers, dem Gericht zu belegen, dass trotz der mehrheitlichen Ortsabwesenheit der Ehegattin eine eheliche Gemeinschaft geführt wurde (E. 3.6.4). Hierzu hat der Beschwerdeführer vor der Vorinstanz, wie auch bereits vor den unteren kantonalen Instanzen, beantragt, dass Zeugenbefragungen der Nachbarn sowie von Personen aus seinem näheren Umfeld durchzuführen seien. Er beantragte zudem eine erneute Befragung von sich und seiner Ehegattin. Diese Beweisanträge wurden von der Vorinstanz pauschal mit dem Argument abgewiesen, dass weitere Befragungen nicht nötig seien, da unbestritten sei, dass sich die Ehegattin unter der Woche im Kanton Wallis aufgehalten habe und erst seit Februar 2018 wieder in der ehelichen Wohnung lebe. Darüber hinaus könne eine Zeugenbefragung auch deshalb unterbleiben, weil dadurch die Widersprüche in den polizeilichen Befragungsprotokollen nicht ausgeräumt werden können (E. 4.5 des angefochtenen Entscheids).
3.6.10. Diese antizipierte Beweiswürdigung (vorne E. 3.4) der Vorinstanz ist verfassungsrechtlich unhaltbar (<ref-law>). Das zentrale Beweisthema des vorinstanzlichen Verfahrens war, ob trotz des unbestrittenen Aufenthalts der Ehegattin in W._/VS eine eheliche Gemeinschaft geführt wurde, mithin, ob trotz räumlicher Entfernung ein Ehewille vorlag. Dem Beschwerdeführer oblag hierfür die Substanziierungslast, weshalb die Vorinstanz die von ihm zur Klärung dieser Beweisfrage angebotenen sachdienlichen Beweismittel nicht im Rahmen einer antizipierten Beweiswürdigung ablehnen durfte. Dies insbesondere vor dem Hintergrund, dass die beantragten Befragungen der Eheleute und weiterer Zeugen geeignet sein können, die Beweisfrage, ob trotz unbestrittener räumlicher Trennung dennoch eine eheliche Gemeinschaft geführt wurde, rechtsgenüglich zu beantworten. Die antizipierte Abweisung der Beweisanträge des Beschwerdeführers durch die Vorinstanz stellt deshalb eine Verletzung seines Anspruchs auf rechtliches Gehör (<ref-law>) dar.
4.
4.1. Die Beschwerde erweist sich nach dem Dargelegten als begründet und ist gutzuheissen. Das angefochtene Urteil ist aufzuheben und die Sache ist zur weiteren Sachverhaltsabklärung (Befragungen) und neuem Entscheid an die Vorinstanz zurückzuweisen.
4.2. Bei diesem Verfahrensausgang sind keine Gerichtskosten zu erheben (<ref-law>). Der Kanton St. Gallen hat dem Beschwerdeführer 1 für das bundesgerichtliche Verfahren eine Parteientschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Das Urteil des Verwaltungsgerichts des Kantons St. Gallen vom 23. Mai 2019 wird aufgehoben. Die Sache wird zur weiteren Sachverhaltsabklärung und zu neuem Entscheid an die Vorinstanz zurückgewiesen.
2.
Für das bundesgerichtliche Verfahren werden keine Gerichtskosten erhoben.
3.
Der Kanton St. Gallen hat dem Beschwerdeführer 1 für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 2'500.-- auszurichten.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons St. Gallen, Abteilung II, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 14. November 2019
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Hahn