2
$\begingroup$

Let G be a weakly-connected directed graph on n nodes such that:

  1. n is odd.

  2. Every node has exactly 2 arrows going into it.

  3. Every node has exactly 2 arrows going out of it.

  4. Between two nodes there is an arrow in at most one direction.

  5. Exactly 2 nodes, call them A and B, have precisely one self-referencing arrow i.e. one of A's arrows points to A. Same for B. These are the only self-references allowed.

  6. Exactly 1 node, C, has both of its outgoing arrows going to the same node, D. Neither C or D can be A or B.

  7. With the exception of nodes A, B, C, the outgoing arrows of a node go to different nodes.

  8. With the exception of node A, B, D, the incoming arrows of a node comes from 2 different nodes.

Under these conditions, is it true that there is a path between any two nodes of G? If so, how does one prove it? If not, what is the simplest counter-example?

As I have no drawing capability, here is a table of 5 nodes representing a graph which I think meets the above criteria. Note that all nodes have 2 outgoing and incoming nodes. Two nodes A, B use one arrow to point to themselves. One node, C, uses 2 of its arrows to point to the same node D. Neither C or D are A or B. Except for A, B, C the outgoing arrows of a node go to 2 different nodes. Except for A, B, D, the incoming arrows of a node come from 2 different nodes.

A: A,G

B: C,B

C: D,D

D: B,E

E: G,F

F: E,A

G: F,C

$\endgroup$
  • $\begingroup$ I think points 4 and 6 contradict..? $\endgroup$ – user1537366 Feb 9 '15 at 11:58
  • $\begingroup$ I'm having a dickens of a time getting my question right. Thank goodness math isn't my day job! Would you expand a bit on your observation? Why are 4 and 6 in contradiction? I'm not saying they aren't, just that I don't see how. $\endgroup$ – odenlou Feb 9 '15 at 12:26
  • $\begingroup$ Ah, you probably meant if there is an edge from $x\to y$ then there is no edge from $y\to x$. But that condition is really not necessary. $\endgroup$ – user1537366 Feb 9 '15 at 12:59
2
$\begingroup$

Your conditions do not guarantee that $G$ is connected, so for example this graph ($G1$) doesn't have a path from $ABCD$ (on the left) to any of the nodes on the right:


$G1: 12$ nodes:

disconnected digraph


Hmm.. I realise $v$ in $G1$ is even, I think I can make an example with $v$ odd... here you are, $G2$:


$G2: 9$ nodes:

disconnected odd-v digraph


$\endgroup$
  • $\begingroup$ I know that the conditions I posted are rather complicated; I have trouble keeping them straight myself. I am untrained in math and especially graph theory, but I don't think the examples given match the question. 3 of the grpahs, while interesting, have an even number of nodes, while the 5 node graph doesn't have the required 2 nodes that self-reference. Please don't be discouraged but continue to help me figure this out. I don't even know how to begin! $\endgroup$ – odenlou Feb 9 '15 at 2:39
  • $\begingroup$ I only posted two graphs. The top one has twelve nodes, the bottom one has nine. $\endgroup$ – Joffan Feb 9 '15 at 3:20
  • $\begingroup$ Oh! The picture with 9 nodes is only ONE graph? But it looks like two. I'm missing a concept. Somehow I need to say that the graph I speak of doesn't have any "gaps". IT must not look like two self-contained little graphs, but be ONE thing, similar to the 5 on the left or 4 on the right. How do I express that as a condition? $\endgroup$ – odenlou Feb 9 '15 at 10:17
  • $\begingroup$ I think the concept I am looking for is something called "weakly-connected". I have updated my question to reflect that. I want to recognize that Joffan answered my question as originally stated and that answer helped clarify what the actual conditions are. $\endgroup$ – odenlou Feb 9 '15 at 11:52
  • $\begingroup$ You're welcome; bear in mind that although I made the disconnectedness easy to see, it could also be somewhat harder to find out that G is not connected.. $\endgroup$ – Joffan Feb 9 '15 at 14:53
1
$\begingroup$

Theorem: Any digraph such that its underlying graph is connected and every node has equal in-degree and out-degree (property A) is Eulerian (there is a directed cycle passing through every edge exactly once).

Suppose $m\in\mathbb{N}$.

Assume the theorem holds true for digraphs with number of edges less than $m$.

Suppose $G$ is a digraph with property A and $m$ edges.

Take any edge $x\to y$ in $G$, as a path $p$. Keep extending the path $p$ until it forms a loop. One can do this because before the loop happens, the last node $z$ of the path will have one more unchosen out-edge than unchosen in-edges. Remove that from the digraph and apply the induction hypothesis to the resulting connected components, to get Eulerian cycles.

For each component, since the digraph was originally connected, each of these components, and hence the cycle, must intersect $p$ at some point. Extend $p$ by stitching the cycle at that point.

Hence $G$ is Eulerian, with Eulerian cycle $p$.

So all graphs with property A is Eulerian, because a singleton graph with no edges is Eulerian, and the above proves the induction step.

Corollary: Any such graph is strongly connected.

$\endgroup$
  • $\begingroup$ My IQ is not equal to your answer, but I will study it and try to puzzle out its meaning. It will probably take me a day or two. Thank you! $\endgroup$ – odenlou Feb 9 '15 at 12:54

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.