# Why can this connected bipartite graph not contain a cycle?

My Professor said that if we have a graph with max degree $\le 2$ , then the graph can only consist of disjoint collection of paths and cycles. Moreover I know a graph is bipartite iff it contains no odd cycle.

So for a bipartite graph G with bi partition $(X,Y)$ such that $|X|=|Y|=n$ ,connected, with max degree 2 , my professor said it thus consists of a single path or cycle.

But I don't understand the justification used in halls theorem, for example, he says choose $S \subset X$ , and consider the graph induced my $S \cup N(S)$

He says, this graph cannot have a cycle because this would contradict the connectedness of G.

How is this to be understood? Did the statement right before not say that it could contain a cycle?

I get why it may be true that it cant hold for all subsets X but consider the bipartite graph with $V=(v1,v2,v3,v4)$ with $E=(v1v4,v1v3,v2v3,v2v4)$

Say we choose $X=\{v1\}$, then $N(X)=\{v3,v4\}$ clearly there isnt a cycle

but $X=\{v1,v2\}$ then $N(X)=\{v3,v4\}$ and $\{v1v3,v3v2,v2v4,v4v1\}$ is a cycle.

So where am I misinterpreting what is being claimed here?

The question is to prove that G has a perfect matching

• what does hall's theorem have to do with the other stuff? Commented Jan 29, 2017 at 21:47
• I updated it to explain Commented Jan 29, 2017 at 21:49

I am assuming that $S$ is a proper subset of $X$ (or $Y$). The reason why $S\cup N(S)$ cannot contain a cycle is that this cycle would constitute a connected component of $G$, and this is impossible because $S\cup N(S)$ does not contain all the vertices, and the graph is connected.
• yeah${}{}{}{}{}$ Commented Jan 29, 2017 at 21:54
• @Quality Note that if $S$ is not a proper subset then there is no contradiction, since $S\cup N(S)=G$ being a connected component of $G$ doesn't contradict connectedness of $G$ Commented Jan 29, 2017 at 21:55