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$.
- If any node is self-connected, we can remove that connection.
- Each non-base node $A_1$ which has less than two connection can be removed.
- Each node $B_1$ which has less than two connection can be removed.
- 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$
- 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$
- 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$
- 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$
- 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$
- 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$
- 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$
- 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$
- 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$.
Best Answer
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.