Hunting for "unsolvable" graph

Question

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. 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$.

Answer 1

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

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

But rule 8 says that you can do this:

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

Answer 2

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.

Answer 3

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.