# 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!

• $G-v \mid v \in V(G)$ is ambiguous. What's going on there? – Newb Dec 19 '13 at 23:23
• $G-v$ is the graph $G$ with $v$ removed, and you look at the sets of all 'one point deletions' from $G$, so $\{G-v|v\in V(G)\}$, where $V(G)$ is the set of vertices of $G$. – Ragnar Dec 19 '13 at 23:32
• This seems to be a restricted version of reconstruction conjecture. – Yong Hao Ng Dec 19 '13 at 23:49

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.

• I think you meant "a graph is bipartite if and only if it contains no cycles of odd length". – Yong Hao Ng Dec 19 '13 at 23:52
• @YongHaoNg you're right, changed it – Ragnar Dec 19 '13 at 23:55
• I think you can solve the case when $G$ is a cycle of odd length. In this case you will get $S$ that has odd number of elements $s$, each a path of even length. Given this information, I think the original $G$ must be a cycle of odd length. For example, take an $s\in S$ and introduce a vertex $u$. Then $G$ can be formed from $s$ and $u$ by joining $u$ to selected vertices in $s$. If $u$ is joined to $\geq 3$ vertices, then removal of one of them will create a cycle, so one of $s'\in S$ has a cycle, a contradiction. If $u$ is isolated, then some $s\in S$ is not a path. – Yong Hao Ng Dec 20 '13 at 0:11
• If $u$ is joined to a vertex $v\in V(s)$, then $G-v$ is disconnected, so an $s\in S$ is not a path. Finally, when $u$ is connected to 2 vertices but does not form a cycle, we can choose some $v\in S$ and delete it so that $s+u-v$ has a cycle. But this means some $s'\in S$ is not a path. So this seems to complete your proof, except that there might be some small issues when $|G|=3$ (should be okay for $|G|\geq 5$). – Yong Hao Ng Dec 20 '13 at 0:13
• Thanks! This clears things up – user3121008 Dec 20 '13 at 0:20

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}$.