1
$\begingroup$

While solving some math problem about graphs, I came up with an interesting question. Maybe it looks a bit hard to understand, but when you visualize how it works, it is pretty simple.

Consider an undirected graph with the following properties:

  • There are two types of nodes: $A$ and $B$.
  • Graph must contain exactly one node $A_P$ and exactly one node $A_Q$ (base nodes of type $A$).
  • Graph can contain arbitrary number of $B_P$ and $B_Q$ (base nodes of type $B$).
  • Let $\text{val}\left(B_k\right)$ be the value of node $B_k$ for any $k\in\left[1,n\right]$ where $n$ is the number of nodes of type $B$ in the graph.
  • Given that $\text{val}\left(B_P\right)$ and $\text{val}\left(B_Q\right)$ are known values.
  • Let $f_1,f_2,f_3,f_4$ be the functions which satisfies the following rules.

Rules

All of these rules have its inverse. This means that if we have some graph $G_1$, we can transform it to any graph $G_2$ for which, if we apply some rule, it bacomes $G_1$.

  1. If any node is self-connected, we can remove that connection.
  2. Each non-base node $A_1$ which has less than two connection can be removed.
  3. Each node $B_1$ which has less than two connection can be removed.
  4. For each non-base node $A_1$ which is connected only to $A_2$ and $A_3$ we can:
    • Remove $A_1$
    • Connect $A_2$ and $A_3$
  5. For each connected nodes $B_1$ and $B_2$ we can:
    • Remove that connection
    • Add arbitrary non-base node $A_1$
    • Connect $A_1$ with $B_1$ and $B_2$
  6. For each connected nodes $A_1$ and $A_2$ we can:
    • Remove that connection
    • Add node $B_P$
    • Connect $B_P$ to $A_1$ and $A_2$
  7. For each non-connected nodes $A_1$ and $A_2$ we can:
    • Add node $B_Q$
    • Connect $B_Q$ to $A_1$ and $A_2$
  8. For each nodes $B_1,B_2,A_1,A_2$ for which $B_1$ is only connected to $A_1$ and $B_2$, and $B_2$ is only connected to $B_1$ and $A_2$ we can:
    • Remove nodes $B_1$ and $B_2$
    • Add node $B_3$ such that $\text{val}\left(B_3\right)=f_1\left(\text{val}\left(B_1\right),\text{val}\left(B_2\right)\right)$
    • Connect $B_3$ to $A_1$ and $A_2$
  9. For each nodes $B_1,B_2,A_1,A_2$ for which $B_1$ is only connected to $A_1$ and $A_2$, and $B_2$ is only connected to $A_1$ and $A_2$ we can:
    • Remove nodes $B_1$ and $B_2$
    • Add node $B_3$ such that $\text{val}\left(B_3\right)=f_2\left(\text{val}\left(B_1\right),\text{val}\left(B_2\right)\right)$
    • Connect $B_3$ to $A_1$ and $A_2$
  10. For each nodes $B_1,B_2,B_3,A_1,A_2,A_3$ for which $B_1$ is only connected to $A_1$ and $A_2$, $B_2$ is only connected to $A_2$ and $A_3$, and $B_3$ is only connected to $A_3$ and $A_1$ we can:
    • Remove nodes $B_1,B_2,B_3$
    • Add nodes $B_4,B_5,B_6$ such that $\text{val}\left(B_4\right)=f_3\left(\text{val}\left(B_1\right),\text{val}\left(B_2\right),\text{val}\left(B_3\right)\right)$, and $\text{val}\left(B_5\right)=f_3\left(\text{val}\left(B_2\right),\text{val}\left(B_3\right),\text{val}\left(B_1\right)\right)$, and $\text{val}\left(B_6\right)=f_3\left(\text{val}\left(B_3\right),\text{val}\left(B_1\right),\text{val}\left(B_2\right)\right)$
    • Add arbitrary non-base node $A_4$
    • Connect $B_4$ to $A_1$ and $A_4$, $B_5$ to $A_2$ and $A_4$, and $B_6$ to $A_3$ and $A_4$
  11. For each nodes $B_1,B_2,B_3,A_1,A_2,A_3,A_4$ ($A_4$ cannot be base node) for which $B_1$ is only connected to $A_1$ and $A_4$, $B_2$ is only connected to $A_2$ and $A_4$, $B_3$ is only connected to $A_3$ and $A_4$, and $A_4$ has exactly $3$ connections we can:
    • Remove $B_1,B_2,B_3,A_4$
    • Add nodes $B_4,B_5,B_6$ such that $\text{val}\left(B_4\right)=f_4\left(\text{val}\left(B_1\right),\text{val}\left(B_2\right),\text{val}\left(B_3\right)\right)$, and $\text{val}\left(B_5\right)=f_4\left(\text{val}\left(B_2\right),\text{val}\left(B_3\right),\text{val}\left(B_1\right)\right)$, and $\text{val}\left(B_6\right)=f_4\left(\text{val}\left(B_3\right),\text{val}\left(B_1\right),\text{val}\left(B_2\right)\right)$
    • Connect $B_4$ to $A_1$ and $A_2$, $B_5$ to $A_2$ and $A_3$, $B_6$ to $A_3$ and $A_1$
  12. We say that graph is "solved" if it is reduced to the following form:
    • There are only nodes $A_P,A_Q,B_1$ where $B_1$ is obtained by applying some of the above rules
    • $A_P$ is only connected to $B_1$, $A_Q$ is only connected to $B_1$, and $B_1$ has only two connections
    • We say that $\text{val}\left(B_1\right)$ is the "solution" of the graph

This is the definition of my graph. The first question I came up with is "Do such a functions $f_1,f_2,f_3,f_4$ exist?" This was not a hard problem. I've already proved these functions exist. The question I couldn't answer is "Is there a graph which satisfies these specifications, but we cannot solve it using the provided rules?" I spent a lot of time trying to find such a graph or prove it doesn't exist, but I couldn't.

For instance, lets solve this graph. enter image description here Let $b_1,b_2,b_3,b_4,b_5$ be the values of corresponding $B$ nodes.

  • Applying rule $10$ on nodes $B_1,B_2,B_5,A_1,A_4,A_3$, we get three new nodes with values $f_3(b_1,b_2,b_5),f_3(b_2,b_5,b_1),f_3(b_5,b_1,b_2)$.
  • Applying rule $8$ two times we get nodes with values $f_1(f_3(b_5,b_1,b_2),b_3)$ and $f_1(f_3(b_2,b_5,b_1),b_4)$.
  • Applying rule $9$ to these two nodes we get node with value $f_2(f_1(f_3(b_5,b_1,b_2),b_3),f_1(f_3(b_2,b_5,b_1),b_4))$.
  • Applying rule $8$ again, we get $f_1(f_2(f_1(f_3(b_5,b_1,b_2),b_3),f_1(f_3(b_2,b_5,b_1),b_4)),f_3(b_1,b_2,b_5))$ which is also the solution of this graph.

I solved a lot of graphs, but I couldn't find any unsolvable graph. Just because of curiosity, I am wondering if we can construct an unsolvable graph, or can we prove it doesn't exist? I don't think the answer may be helpful to anyone, so don't get this question too serious. Only if you have a time to spend, you can help me to prove it.

Edit

Because it may be confusing what are $A_P$ and $A_Q$, $B_P$ and $B_Q$, what is the difference between base and non-base nodes, what can be removed and what cannot, I will explain it carefully. These are the questions someone may ask (while I still think these explanations are not necessary because the above definitions should be enough):

  • So is the requirement simply that there are at least two nodes of type $A$? Yes, there should be at leat two nodes of type $A$. Maybe it is confusing what does $A_P$ and $A_Q$ stand for. To explain that, lest say all non-base nodes of type $A$ (all "removable" nodes) have value $0$ (for example) and $A_P$ has value $1$ and $A_Q$ has value $2$. If we asign values in this way, it means that there must be exactly one node of type $A$ which has value (vertex weight) of $1$ and exactly one node $A$ shich has value $2$. Other $A$ nodes (if exist) must have value $0$.
    Note that these value are just an example of how to find the difference between base and non-base nodes. Simply, if you asign these value, when it says node $A_P$ it means node $A$ with value $1$. Because there must be exactly one node $A$ with value $1$, it is well-defined what is that node.
    However, in some rules (for example $8$, $9$, $10$, $11$) it doesn't say if $A_1$ and $A_2$ are base or non-base nodes, so it applies to both base and non-base nodes.
  • Is there a difference between $B_P$ and $B_Q$ nodes. It depends on what are their values. Because they are of the same type, if they have same value, there is no difference between them. But, it is not important. It really depends on what functions $f_1,f_2,f_3,f_4$ you choose. Similary as $A_P$ and $A_Q$, nodes $B_P$ and $B_Q$ is different from other $B$ nodes because they have different value. Their value are known constants, but no matter how you chose it, the answer to the main question will not be changed (only functions $f_1,f_2,f_3,f_4$ will be affected), so their values are not important. Lets say $\text{val}(B_P)=b_p$ and $\text{val}(B_Q)=b_q$ where $b_p$ and $b_q$ are known constants. So, all $B$ nodes in the graph which have value $b_p$ will be nodes $B_P$ (note that there can be arbitrary number of nodes $B_P$). Also, all nodes of type $B$ which has value $b_q$ are nodes $B_Q$ (there can be arbitrary number of nodes $B_Q$ no matter how many nodes $B_P$ are in the graph).
    However, in difference from $A_P$ and $A_Q$, base nodes of type $B$ can be added and removed. They can be added explicitly using rules $6$ and $7$, but I have also proved that it is possible to chose $f_1,f_2,f_3,f_4$, so that they can be added using reversed rules from $8$ to $11$. Similary, base nodes of type $B$ can be removed using rules from $8$ to $11$ and replaced with some other $B$ node(s) according to rules.
  • Do base nodes $B$ come in pairs? No, I mentioned it several times. You can have $m$ nodes $B_P$ and $n$ nodes $B_Q$ for all $m,n\in\mathbb{N}_0$.
  • If $A_P$ and $A_Q$ are different from other $A$ nodes, does it mean there are actually three types of nodes? You may define them as a new type of nodes, but then some rules that include arbitrary (base or non-base) nodes $A$ will be broken. If you define them as a new type, you have to change some rules. There are a reason why I call them base-nodes of type $A$ instead of, for example, nodes of type $C$.
$\endgroup$
  • 8
    $\begingroup$ To me, I feel the setup is still very confusing and unclear (and unmotivated). But I am only one person, maybe it will make sense to others. $\endgroup$ – Morgan Rodgers Nov 11 '16 at 3:10
  • 2
    $\begingroup$ I've read this over and over (before and after I made the previous comments) and still don't understand what makes the $B_{P}$ and $B_{Q}$ nodes different from the $B_{i}$ nodes. I also don't understand if the "Rules" are giving rules that must be satisfied by the functions $f_{i}$ ($1 \leq i \leq 4$), or if they are only giving the procedure for reducing ("solving") the graph. $\endgroup$ – Morgan Rodgers Jul 2 '17 at 1:08
  • 3
    $\begingroup$ In rule 10 I think you have the subindices wrong, check it out. $\endgroup$ – Sergio Enrique Yarza Acuña Jul 7 '17 at 18:01
  • 4
    $\begingroup$ This question needs to be completely rewritten. $\endgroup$ – mercio Jul 9 '17 at 8:35
  • 2
    $\begingroup$ @Mathematician171 It can be edited by people other than the asker. I don't think it's clear at all. Why are there no $B_{P}$ or $B_{Q}$ nodes in the example? And what are the $f_{i}$? It actually seems like the $f_{i}$ are completely unrelated to everything and can be ignored, but I'm not sure. $\endgroup$ – Morgan Rodgers Jul 10 '17 at 17:59
3
$\begingroup$

Since this seems to be the question that won't die, I will post with an analysis of the issues with how the problem is posed. Until the whole thing is completely rewritten, I think this is the best answer that this question can hope for.

  1. What rules are the $f_{i}$ supposed to follow? Why do we even have the $f_{i}$?
  2. Are there two types of nodes ($A$ and $B$) or six types of nodes ($A_{P}$, $A_{Q}$, $A_{i}$, $B_{P}$, $B_{Q}$, $B_{i}$)? Or are there only four types, with $A_{P}$ and $A_{Q}$ (and $B_{P}$/$B_{Q}$) being essentially indistinguishable?
  3. If $\mathrm{val}(B_{P})$ and $\mathrm{val}(B_{Q})$ are known, does that mean the other vertices' values are unknown? Then how do we compute the values of these mysterious $f$ functions?
  4. There are arbitrarily many vertices $B_{P}$ and $B_{Q}$; do they all have the same value? Can a node $B_{i}$ have the same value as $B_{P}$ or is that off-limits? (In fact the more I read the poster's clarifications on the $B$ nodes, the less I understand.)
  5. On that topic, in the example given, we have $B_{1}$, $\ldots$, $B_{5}$; no $B_{P}$ or $B_{Q}$ nodes? Or are there set global values $b_{P}$ and $b_{Q}$ such that, if a $B$ node has one of these values, they become a $B_{P}$/$B_{Q}$ node and start following those rules?

The question could maybe be clarified a lot by removing all references to the $f_{i}$ functions and the valuation function, since they aren't at all relevant to the reduction operation. Maybe then the roles of the different types of vertices in this process could be explained more clearly.

$\endgroup$
  • 1
    $\begingroup$ @MorganRodgers. My edit is rejected. According to your questions, I'm really starting to believe that you are joking or trolling. Did you even read all the answers? How is it still not clear to you? "The rules don't give any requirements on the $f_i$" - that's wrong. The requirement is to satisfy the $12$ given rules. "A single node can be a $B_i$, $B_P$,and $B_Q$ node, all at the same time?This does not clarify things for me." - I cannot see what is wrong here?For example $5$ is both real and natural number, isn't it? $\endgroup$ – user471557 Sep 20 '17 at 22:26
  • 1
    $\begingroup$ @user471557 Not trolling, not joking. The rules tell how the $f_{i}$ are used to get values for the new vertices, but don't give any requirements for the $f_{i}$. And the valuation isn't used for anything (at least, not for anything related to answering the question). It gives the impression that there is maybe a simple question hidden somewhere among all the irrelevant details and complications. That question might be interesting (or not, I am totally honest about not being able to decipher what this question is). $\endgroup$ – Morgan Rodgers Sep 21 '17 at 2:19
  • 1
    $\begingroup$ I don't have time to troll people, I really would like to see this question pared down to the relevant details. $\endgroup$ – Morgan Rodgers Sep 21 '17 at 2:20
2
$\begingroup$

To summarize, we have a class of undirected graphs. Each node of the graph has a type (which may be $A$ or $B$) and a value (which is a number). There are two distinct special values $a_p$ and $a_q$; there is exactly one node of type $A$ with weight $a_p$ and one with weight $a_q,$ designated (respectively) $A_P$ and $A_Q.$ There are two numbers $b_p$ and $b_q$ that are special values for nodes of type $B,$ but there is no restriction on how many nodes of type $B$ have either of these values.

There is a set of rules by which one graph may be transformed into another. There are also functions $f_1: \mathbb R\times\mathbb R\to\mathbb R,$ $f_2: \mathbb R\times\mathbb R\to\mathbb R,$ $f_3: \mathbb R\times\mathbb R\times\mathbb R\to\mathbb R,$ and $f_4: \mathbb R\times\mathbb R\times\mathbb R\to\mathbb R$ that are part of these rules. (I am assuming here that the node values are real numbers; if that is not the case, replace $\mathbb R$ with the correct set wherever it appears.)

Rules 1, 2, and 3 allow the removal of self-connections and the removal of any node (other than the special nodes $A_P$ and $A_Q$) if that node has one connection or no connections. The other rules are represented by the following figures, in which the shapes of nodes are used as an added visual cue to which nodes are removed and which are added, according to the following legend:

Note that the nodes that are removed or added must have only the connections shown in the figures, but any other node may have any number of connections, which are unaffected by the rule. In the figures, node labels $A_1, A_2,$ etc. are applied to arbitrary nodes of type $A$; node labels $B_1, B_2,$ etc. are applied to arbitrary nodes of type $B,$ with values $b_1, b_2,$ etc., respectively.

Rule 4:

Rule 5:

Rule 6:

(The node labeled $B_P$ has weight $b_p.$)

Rule 7:

(The node labeled $B_Q$ has weight $b_q.$)

Rule 8:

where $b_3 = f_1(b_1,b_2).$

Rule 9:

where $b_3 = f_2(b_1,b_2).$

Rule 10:

where $b_4 = f_3(b_1,b_2,b_3),$ $b_5 = f_3(b_2,b_3,b_1),$ and $b_6 = f_3(b_3,b_1,b_2).$ (The weight of node $A_4$ cannot be $a_p$ or $a_q$.)

Rule 11:

where $b_4 = f_4(b_1,b_2,b_3),$ $b_5 = f_4(b_2,b_3,b_1),$ and $b_4 = f_3(b_3,b_1,b_2).$ (The weight of node $A_4$ cannot be $a_p$ or $a_q$.)

It is given in the question that every transformation described by the above rules can be reversed, that is, there is an "inverse rule" for each of the rules 1 through 11.

Note that Rule 11 is the inverse of Rule 10 if and only if $f_4(f_3(b_1,b_2,b_3),f_3(b_2,b_3,b_1),f_3(b_3,b_1,b_2)) = b_1$ for all $b_1,b_2,b_3 \in \mathbb R.$ No such assertion has been made about $f_3$ and $f_4$; in fact, any functions $f_1,f_2,f_3,$ and $f_4$ would fit the stated transformation rules as long as each function takes the correct number of parameters. Depending on the complete definitions of $f_3$ and $f_4,$ then, the inverse of Rule 10 may be Rule 11 or some other rule.

Also note that in the inverse rule of Rule 8 or Rule 9, neither $b_1$ nor $b_2$ is a function of $b_3$ unless $f_1$ or $f_2$ (respectively) is an injective function. Such functions of type $\mathbb R\times\mathbb R\to\mathbb R$ exist, but they are not "nice" functions, so it seems reasonable to suppose that the inverses of Rule 8 and Rule 9 are nondeterministic. The inverses of Rules 2, 3, and 4 seem clearly nondeterministic, so it seems reasonable to suppose that Rule 5 is too.

It is impossible to transform a graph to the form specified in Rule 12 if any type-$B$ node has three or more connections, since the only rule that can apply to such a node is Rule 5, which does not change the number of connections.

If there is no $B$-node with three or more connections, then it seems simple enough to use Rules 5, 6, 8, 9, and their inverses to transform any graph into one in which every $A$-node (except possibly $A_P$ and $A_Q$) has at least three connections, each to a $B$-node, and each $B$ node is connected to exactly two $A$-nodes. And that's as far as I have gotten yet.

$\endgroup$
2
+250
$\begingroup$

This is not a complete answer, but may provide some useful information.

In the example, after applying rule 10, one gets the graph

enter image description here

But rule 8 says that you can do this:

enter image description here

So, I don't see where you can apply rule 8 in the new graph.

$\endgroup$
  • 1
    $\begingroup$ @SergioEnriqueYarzaAcuña. Comments are not a place for such discussion. You are basically asking me to solve the problem for you. If you don't know how the graph should look like, then why did you answer the question? Please delete your answer to not gain the bounty points again. Last time you got 250 rep for no reason, please avoid it this time and delete your answer. $\endgroup$ – user471557 Sep 20 '17 at 10:35
  • 1
    $\begingroup$ For what it's worth, I support this answer whole-heartedly. Keep the bounty. $\endgroup$ – Morgan Rodgers Sep 20 '17 at 16:14
  • 2
    $\begingroup$ To users who keep flagging this post. A moderator should not delete upvoted material on one or two persons opinion alone, and we are for very good reasons reluctant to create new policies on a whim. Vote to delete yourself. And/or ask for more opinions in the C.R.U.D.E. chatroom. The site is first and foremost COMMUNITY MODERATED so we should let the community decide. You can also draw attention to the dilemma in Meta, as the case is admittedly unusual. $\endgroup$ – Jyrki Lahtonen Sep 20 '17 at 21:52
  • 4
    $\begingroup$ I believe the first picture in this answer, call it $G_2,$ is a correct application of rule 10 to $A_1,A_3,A_4$ in the original graph (and the only correct application to those nodes, up to the choice of labels to assign to the new nodes). Moreover, it is clearly impossible to apply rule 8 immediately to $G_2,$ because rule 8 requires two B nodes with a link directly between them and there is no such pair of nodes in $G_2.$ $\endgroup$ – David K Sep 21 '17 at 13:18
  • 1
    $\begingroup$ Meta thread at math.meta.stackexchange.com/questions/27028/… $\endgroup$ – Gerry Myerson Sep 22 '17 at 6:40

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.