0
$\begingroup$

I'm working on a problem in logic and it reduces to proving that a certain infinite graph is connected. The graph has the following properties:

  1. It is bipartite
  2. It is not necessarily finite (or countable or locally finite).
  3. It has no degree zero vertices
  4. It has no infinite rays
  5. It is acylic

My question is a bit open-ended. I am finding it difficult to prove the connectedness. I was wondering if there are any necessary and sufficient conditions to ensure connectedness. In other words, if I could try proving a property on graph that is equivalent to its connectedness.

Improve this question
$\endgroup$
2
  • $\begingroup$ given any graph $G$ with the properties you gave, can't you just consider the graph $G\sqcup G$, which is just two disjoint copies of $G$? I think $G\sqcup G$ will also satisfy all the properties you gave but will not be connected. $\endgroup$
    – mathworker21
    Apr 22 at 18:37
  • $\begingroup$ @mathworker21 I am asserting that any graph with these properties is connected. I want to know if there is some property P (that is weaker than connectedness in general) such that such a graph satisfies P iff it is connected. $\endgroup$
    – Faustus
    Apr 23 at 21:20

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.