We have an undirected graph $G = (V, E)$ partitioned into two non-empty subsets $V_1 \cup V_2 = V$. For this graph it holds that $(V_1 \cup V_2 = V) \implies (\exists v_1, v_2 : v_1 \in V_1 \land v_2 \in V_2 \land (v_1,v_2) \in E)$. So for every partition some $v_1 \in V_1$ is connected to some $v_2 \in V_2$. We need to show $G$ is connected, i.e.: to show that there is a path between any two elements in the graph.
This problem came from a problem set in a course on discrete mathematics. I solved the problem in two ways. One being by contradiction. Namely by assuming that the graph is not connected, then there exists a partition $V_{1}$ and $V_{2}$ such that no edge $(v_{1}, v_{2})$ exists with $v_{1} \in V_{1}$ and $v_{2} \in V_{2}$ which means the assumption that the graph is not connected is false. And so the graph must be connected.
The other approach I came up with is based on induction and I would like to put this approach up to scrutiny. In this approach I incorporate the definition that for all partitions there is a $v_1 \in V_1$ and $v_2 \in V_2$ with $(v_1, v_2) \in E$ in an induction hypothesis. The induction hypothesis (IH) $P(n)$ being that "for any partition $V_1$ with $n$ elements these elements are part of an induced (sub)graph $G[V_1]$ which is connected and there exists a $v_1 \in V_1$ and $v_2 \in V_2$ with $(v_1, v_2) \in E$". $G[V_x]$ is the induced subgraph of $G$ with elements in $V_x$.
Since the partitions are defined to be non-empty the base case contains one element. Applying the induction hypothesis to the base case $P(1)$ one gets "for any partition $V_1$ with 1 element this element is part of an induced (sub)graph $G[V_1]$ which is connected and there exists a $v_1 \in V_1$ and $v_2 \in V_2$ with $(v_1, v_2) \in E$", which is true since any graph of one element is trivially connected and furthermore by definition this element is connected to some element $v_2 \in V_2$. So there exists no element which is not connected to some other element, i.e.: every element in $V$ is connected to some other element in $V$. Since we have added $(v_1, v_2)$ to a connected $G[V_1]$ we get that $G[V_1 \cup v_2]$ is connected. By definition the induced subgraphs consisting of two elements in $V_1$ are connected to some element $v_2 \in V_2$. And so $P(1) \implies P(2) $.
Generalising we get that $P(n) = $ "for any partition $V_1$ with $n$ elements these elements are part of an induced (sub)graph $G[V_1]$ which is connected and there exists a $v_1 \in V_1$ and $v_2 \in V_2$ with $(v_1, v_2) \in E$", which implies that every induced subgraph $G[V_1 \cup v_2] = (V_1 \cup {v_2}, E_1 \cup (v_1, v_2))$ of $G$ with $n + 1$ elements is connected and furthermore by IH these subgraphs contain some element connected to some element in $G[V_2 \setminus v_2]$. And so $P(n) \implies P(n + 1)$.
And now we have that $P(1)$ and $P(n) \implies P(n + 1)$ and so $P(n)$ holds for all $n \leq \#V - 1$ (since partitions are non-empty). To finish things off we consider $P(m - 1)$ with $m = \#V$. We have shown that all induced subgraphs $(V_1, E_1)$ of $G$ of size $m - 1$ are connected and by IH there is some element in this subgraph connected to an element in $V \setminus V_1$. There is only one element left and since this element is connected to a connected subgraph the graph $G$ is connected.
I can't find anything wrong with this reasoning but I'm not certain it's correct either. If anyone can point out something wrong with this, or provide a better induction hypothesis or something of that nature it would be much appreciated :).
Your induction argument as phrased is confusing to me. From what I'm reading, it seems to me you're saying that $P(n)$ is the statement "for any $n$-element subset $V_1$ of the vertex set, the elements of $V_1$ span a connected subgraph". As I'm interpreting it, this is false. For instance the statement $P(2)$ would tell you that your graph is complete, which needn't be the case.
The other way I might interpret your solution is that $P(n)$ would be the statement "for any $n$-element subset $V_1$ of the vertex set, the elements of $V_1$ are connected within the larger graph". Now the statement $P(2)$ is equivalent to the graph being connected, which is the thing you were trying to prove.
I think a better approach would be to make purposeful choices in what your subsets are, i.e. we choose the subsets of vertices rather than letting them be arbitrary. So I'm going to say that $P(n)$ is the statement that "there exists an $n$-element subset $V_n$ of the vertex set such that $V_n$ spans a connected subgraph". You can pick $V_1$ arbitrarily to prove $P(1)$. Then as long as there are more than $n$ vertices in the graph, we can always construct $V_{n+1}$ from $V_n$ by adding the special connected vertex in the complement of $V_n$. This gives us that $P(n) \implies P(n+1)$.
A note though is that this induction approach only helps you to prove the statement for finite graphs because the subgraphs you consider, i.e. the subgraphs you prove are connected, are always finite. The induction process will end if you can reach $\#V$ in finitely many steps, but otherwise you're lost. So the contradiction approach you mentioned is almost certainly the better way to go in general.