0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ what does hall's theorem have to do with the other stuff? $\endgroup$
    – Asinomás
    Commented Jan 29, 2017 at 21:47
  • $\begingroup$ I updated it to explain $\endgroup$
    – Quality
    Commented Jan 29, 2017 at 21:49

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ So how does my example contradict this? only in that I chose not a proper subset? $\endgroup$
    – Quality
    Commented Jan 29, 2017 at 21:54
  • $\begingroup$ yeah${}{}{}{}{}$ $\endgroup$
    – Asinomás
    Commented Jan 29, 2017 at 21:54
  • 1
    $\begingroup$ Makes sense, as long as assuming proper subset is okay $\endgroup$
    – Quality
    Commented Jan 29, 2017 at 21:55
  • $\begingroup$ @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$ $\endgroup$ Commented Jan 29, 2017 at 21:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .