Proof - Bipartite Graphs Let $G$ be an arbitrary, unknown graph with at least two vertices. Suppose you are given the subgraphs in the set $S = \{G - v | v \in V(G)\}$, but the vertices in the subgraphs are not labeled, and you do not know which vertex is missing in which subgraph. Is it possible to determine whether $G$ is bipartite? 
The solution is that it is possible, but the professor doesn't provide additional explanations. Any help would be greatly appreciated!
 A: You know that a graph is bipartite if and only if it contains only cycles of even length. If (at least) one $s\in S$ contains a cycle of odd length, you know $G$ is not bipartite. If for all $s\in S$, $s$ contains only even cycles, you want $G$ to be bipartite. Suppose on the contrary that $G$ does have an odd cycle. If it does not visit al $v\in V$, you can select a $v'$ not in the cycle, and look at $G-v'$. This contains a odd cycle, so we have a contradiction. So we know that $G$ can only contain odd cycles of odd length which visit all vertices. If $|G|$ is even, we're done. when the only odd cycle visits all vertices, we have a problem. If there is at least one other edge, we know that is devides the long odd cycle in two halfs, one of which has even length, and together with the extra edge, we have a shorter cycle of odd length, so contradiction. The only case where we cannot (see edit) determine whether $G$ is bipartite or not is when $G$ is a cycle of odd length. This can easily be seen when looking at $G=K_3$.
EDIT In fact, it is possible in another way: Count the total number of edges in all thesubgraphs. If this is equal to $n(n-2)$, where $n$ is the size of $G$ and $n-1$ the size of the subgraphs, $G$ must have had $n$ edges. If it had at most $n-1$ edges, you would not count $n(n-2)$ edges, because $n(n-2)$ is the maximum, and it is only reached when $G$ had $n$ edges.
A: Claim $G$ is not bipartite if and only if one of the following two happens:


*

*$S$ contains a graph which is not bipartite
or

*There exists a $k \geq 1$ so that all graph in $S$ are $P_{2k}$, where $P_n$ denotes the path graph. 


Proof
$\Rightarrow$:
Since $G$ is not bipartite then it contains an odd cycle.
Case 1: $G$ is not a cycle graph. Then, there exists a vertex $v$ which is not on the shortest odd cycle. Then $G -v$ is in $S$ and not bipartite.
Case 2: $G$ is a cycle graph. Then $G=C_{2k+1}$ for some $k$, and then all graphs in $S$ are $P_{2k}$. 
$\Leftarrow$: 
If $S$ contains a graph which is not bipartite, this is a subgraph of $G$ and hence $G$ cannot be bipartite.
If all graphs in $S$ are $P_{2k}$, then $G$ has $2k+1$ vertices. Then it is easy to prove that $G$ is connected and that every vertex in $G$ has degree $2$. 
Thus $G$ is connected and every vertex has degree $2$, which means that $G$ is a cycle graph. Thus $G=C_{2k+1}$. 
