I'm completing a graph theory assignment, and one of the problems states,

Prove that a tree $T$ has a perfect matching if and only if $o(T-v) = 1$ for every $v \in V (T)$.

I'm not asking for help answering this question, but rather for help understanding the notation. What does $o(G)$ usually mean in graph theory? If it has multiple conventional meanings, which are the most common?

One thought I had was that it could be the number of odd disconnected components left after removing some vertices, but I believe that following that definition's implications has lead me to a disproof of the statement in the question, so I don't think that's correct.

  • $\begingroup$ Please do not answer the homework question for me. I would like to figure it out myself once I am sure I understand precisely what it is asking. $\endgroup$ – Kevin Dec 5 '14 at 3:22
  • 2
    $\begingroup$ The $o(G)$ is referring to the number of components of odd order in $G$. $\endgroup$ – ml0105 Dec 5 '14 at 3:26
  • 1
    $\begingroup$ Positive. I had this homework question last semester. I just double checked as well. Theorem 3.3.3 of West may offer some clarification as well. $\endgroup$ – ml0105 Dec 5 '14 at 3:34
  • $\begingroup$ Thank you for answering my question, @ml0105! $\endgroup$ – Kevin Dec 5 '14 at 3:44

I think that $o(G)$ refers to the number of components of G which have an odd number of vertices (also denoted by odd($G$)).

In this case, the graph induced by $T-v$ has at most $1$ connected component with an odd number of vertices.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.