2
$\begingroup$

If any countably infinite simple digraph $G$ is such that every weakly connected, spanning subgraph of $G$ is equal to $G$ then must $G$ always be a polytree (an orientation of an undirected tree graph)? Also if so, is this then a necessary condition for any simple-digraph to be a polytree? I.e. do we get:

$$\text{ Every connected spanning subgraph of }G\text{ equals }G\iff G\text{ is a polytree}$$

Where again $G$ is any countably infinite simple directed-graph. It seems like both of these should be true intuitively to me. Yet I'm having trouble proving them. If this is actually false could someone provide a counter example for me? Or if its true, point me in the right direction towards proving it?

$\endgroup$
2
$\begingroup$

No, because $G$ might not be weakly connected at all. Then your condition holds vacuously, since there are no weakly connected spanning subgraphs.

On the other hand, if you assume that $G$ is weakly connected, then the answer is yes in both directions (and the cardinality of $G$ is irrelevant). First of all, you might as well pretend your graph is undirected, since all of the properties you ask about are just properties of the underlying undirected graph. The claim is then that a connected (undirected) graph $G$ is a tree iff $G$ is the only connected spanning subgraph of $G$.

First, suppose $G$ is a tree. If $H$ is a proper subgraph that is connected and spanning, consider some edge of $G$ that is not in $H$, between two vertices $v$ and $w$. Since $H$ is spanning and connected, it contains a path from $v$ to $w$. Combining that path with the edge from $v$ to $w$ in $G$, we get a loop in $G$, which is a contradiction.

Conversely, suppose $G$ is the only connected spanning subgraph of $G$. Since $G$ is connected, it has a spanning tree $T$. Then $T$ is a connected spanning subgraph of $G$, so $T=G$, and thus $G$ is a tree.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Doesn't $G$ having weakly connected spanning subgraph imply $G$ is connected? $\endgroup$ – user3865123 Mar 9 '18 at 8:44
  • $\begingroup$ Oh I see, if $G$ was not weakly connected the LHS would hold trivially and yet it would imply that $G$ was a polytree and thus weakly connected a contradiction. $\endgroup$ – user3865123 Mar 9 '18 at 8:44

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.