# Non isomorphic graphs with equal cycle matrices

everyone.
I have solved a following problem, the solution seems too simple, so I am suspicious, that I am making a mistake. Would be very greateful, if someone cheked the solution.

So, the problem : do there exist two simple, non isomorphic graphs, which cycle matrices are equal and every edge is contained in some cycle.

The solution : let two graphs be $G_1$ and $G_2$. Their corresponding cycle matrices are $C_1$ and $C_2$. Since they are aqual, let $C_1 = C_2 = C$. Let $A_1$ and $A_2$ be icidence matrices of $G_1$ and $G_2$. From theory it is known that $C \cdot A_1^T = 0$ and $C \cdot A_2^T = 0$. But, then $C \cdot A_1^T = C \cdot A_2^T$ and $A_1^T = A_2^T$ and $A_1 = A_2$. But this means that $G_1$ and $G_2$ are isomorphic. So the answer is no, such graphs do not exist.

Edit : since all matrices contain only values ${0,1}$, multiplication is done in the way, that $0 \cdot 0 = 0$, $1 \cdot 0 = 0$, $0 \cdot 1 = 0$ and $1 \cdot 1 = 1$

About the cycle matrix. Let the graph $G$ have $m$ edges and let $q$ be the number of different cycles in $G$. The cycle matrix $B = [b_{ij}]_{q \times m}$ of $G$ is $(1,0)$ matrix of order $q \times m$ with $b_{ij} = 1$ if the $i$th cycle includes $j$th edge and $b_{ij} = 0$ otherwise.

• First line should be "Hallo, everyone". I have written that way dont know why it doesnt display as it should. – Jevgenijs Strigins Nov 17 '13 at 17:27
• What is the cycle matrix? – Jernej Nov 17 '13 at 23:57
• I edited my question with definition of cycle matrix. – Jevgenijs Strigins Nov 18 '13 at 7:36
• Title says "isomorphic," body asks for "non-isomorphic". Please edit one or the other. – Gerry Myerson Nov 18 '13 at 8:09
• If $G_1$ is a cycle of length 3, and $G_2$ is a cycle of length 3 together with a 4th vertex (either isolated, or adjacent to one of the vertices in the 3-cycle), then the graphs have the same cycle matrix, but are not isomorphic, right? – Gerry Myerson Nov 18 '13 at 8:14

## 1 Answer

I'm not entirely sure I have the right definition of cycle --- I'm assuming that something like abcadea (where the letters stand for vertices) doesn't count as a cycle, since it decomposes into two cycles, abca and adea. If I have it right, then there are connected counter-examples. Let $G_1$ be three triangles sharing a single vertex. Let $G_2$ also consist of three triangles, with the 1st and 2nd having one common vertex, the 2nd and 3rd having a different common vertex. Each graph has 9 edges forming 3 cycles, and the same cycle matrix $$\pmatrix{1&1&1&0&0&0&0&0&0\cr0&0&0&1&1&1&0&0&0\cr0&0&0&0&0&0&1&1&1\cr}$$ but the graphs are clearly not isomorphic, as only $G_1$ has a vertex of degree 6.