15
$\begingroup$

question

I have identified two ways of showing it isomorphic but since it is a 9 mark question I dont think i have enough and neither has our teacher explained or given us enough notes on how it can be proven.

My answers so far below:

It is isomorphic as the Number of vertices on both graphs are 6 and the number of edges on both of the graphs are both 7.

Degree of nodes:

Deg (A) = 1 and Degree (T) = 1

Deg (B) = 3 and Degree (U) = 3

Deg (C) = 1 and Degree (Y) = 1

Deg (D) = 2 and Degree (V) = 2

Deg (E) = 1 and Degree (Z) = 1

Deg (F) = 3 and Degree (W) = 3

Deg (G) = 1 and Degree (X) = 1

Is the degree of nodes correct the way I have linked them?

Is what i have wrote above correct and enough or can more be explained? Please give solution to this question. Thanks.

$\endgroup$
  • $\begingroup$ It's hard to say, depends on how explicit the answer has to be to be accepted. Just the degree of nodes is not enough (consider some $k$-regular graphs with the same number of vertices), however, you certainly do give a valid correspondence, and I doubt you were required to enumerate all $\binom{7}{2}$ possible edges to show that it is an isomorphism. $\endgroup$ – dtldarek Aug 19 '13 at 13:46
  • 4
    $\begingroup$ Your definition of isomorphic is wrong: You need a bijection $f:\ V\to V'$ with $\{v_1,v_2\}\in E$ iff $\{f(v_1),f(v_2)\}\in E'$. (According to your definition a graph with zero edges would be isomorphic to any graph with the same number of vertices.) $\endgroup$ – Christian Blatter Aug 19 '13 at 13:50
  • $\begingroup$ @dtldarek i am getting mixed answers, do i have to show the degree of nodes or not to prove they are isomorphic? We didn't go into too much detail in class so I dont think i have to show too much $\endgroup$ – Jay Aug 19 '13 at 13:57
  • $\begingroup$ @ChristianBlatter I dont know about the definition, this was taken from a previously done exam paper $\endgroup$ – Jay Aug 19 '13 at 13:58
  • 1
    $\begingroup$ @Jay Degrees might be useful in proving two graphs are not isomorphic, however, it is not necessary to show that two graphs are. If you want to use the definition (e.g. see Wikipedia), then you need to construct $f$ (which you implicitly did by aligning corresponding vertices in the same rows, however I am not sure if that would be accepted) and then show that $\{u,v\} \in E$ if and only if $\{f(u),f(v)\} \in E'$ (brute-force approach would be to write a line for each of 21 possible edges). $\endgroup$ – dtldarek Aug 19 '13 at 14:08
22
$\begingroup$

Unfortunately, two non-isomorphic graphs can have the same degree sequence. See here for an example. Checking the degree sequence can only disprove that two graphs are isomorphic, but it can't prove that they are. In this case, I would just specify my isomorphism (which you've basically done, by identifying the vertices A and T, B and U, and so on) and then show that two vertices are connected by an edge in the original graph if and only if they are connected in the image. It's a little tedious, but should be something you can apply in general to these kinds of problems.

$\endgroup$
  • $\begingroup$ So the degree of nodes bit I should leave out when proving 2 graphs are isomorphic? But only do that when i am disproving? $\endgroup$ – Jay Aug 19 '13 at 13:42
  • $\begingroup$ Also can you list down for me please what I need to show to prove two graphs are isomorphic? So I have done: - Number of vertices - Number of edges $\endgroup$ – Jay Aug 19 '13 at 13:43
  • 1
    $\begingroup$ @Jay That's exactly right about when to examine the degree list. As for your second question: first, make sure they have the same number of vertices and edges. Then, if you're not sure if they're isomorphic, you can examine the degree list to check that they're not. If the degree list matches up, then I'd suggest starting to find which vertices "look the same" and match them up. Once you've got what vertices you think correspond in the graphs, then try to show that if two vertices are connected, then the vertices you matched them with are also connected. $\endgroup$ – Devlin Mallory Aug 19 '13 at 13:45
  • $\begingroup$ Okay I see, and that should be sufficient for the number of marks to this question? $\endgroup$ – Jay Aug 19 '13 at 13:48
  • 1
    $\begingroup$ I'd just say let the first graph have vertex set $V_1$, the latter $V_2$, let $f:V_1 \to V_2$ by $f(A)=T$, $f(B)=U$, and so on. And again, you can't just say the degrees are the same so they're isomorphic. $\endgroup$ – Devlin Mallory Aug 19 '13 at 13:55
8
$\begingroup$

To show that the two graphs are isomorphic, apply the given definition. Let's call the graph on the left $G[V_1,E_1]$, and the graph on the right $G[V_2,E_2]$. Now give an explicit bijection $$f:\ V_1\ \longrightarrow\ V_2,$$ and show that if $\{e_1,e_2\}\in E_1$, then $\{f(e_1),f(e_2)\}\in E_2$.

Checking that $\operatorname{Deg}(e)=\operatorname{Deg}(f(e))$ for all $e\in V$ is not sufficient: Given an isomorphism $f$, we obtain another bijection $g:\ V_1\ \longrightarrow\ V_2$ by switching $U$ and $W$, that is; $$g(e)=\left\{\begin{array}{cc}W&\text{ if }f(e)=U\\U&\text{ if }f(e)=W\\f(e)&\text{ otherwise}\end{array}\right.$$ The degrees are preserved, but this is not an isomorphism.

$\endgroup$
2
$\begingroup$

First Make Adjacency matrix for both graphs.

These matrices would be square and symmetrical. (If No multiple or directed edges)

The main diagonal would be all zeroes (if no loops)

if number of 1s and 0s are not the same in both matrices then its not isomorphic surely. If they are same then it may be isomorphic.

Take any one of the matrices.

Now you can swap 2 coloumns of this matrix but when you do that you must also swap the same rows.

So while swapping row2 and row3, you should immediately swap col2 and col3 as well. Order of swapping doesnt matter. Since its square matrix, all columns will have corresponding rows.

Doing this would simply swap the vertex's position in adjacency matrix and so changing the mapping of each vertex.

By use of our pattern finding ability we can choose which rows and columns to swap so that one matrix would look exactly like the other. You would get it in max 3-4 swaps.

Its quite easy since they are square symmetrical.

If they are not isomorphic then you might try to swap rows and cols endlessly trying to match the pattern but by little intuition you can avoid that.

They are isomorphic if adjacency matrix look same. This matrix would give you the mappings.

So its like trying to find a mapping from all possible mappings of one graph, that look exactly like the other adjacency matrix by cleaverly swapping position of vertices (by swaping rows and cols). Does not work so good for huge graphs.

$\endgroup$
  • $\begingroup$ "...you might try to swap rows and cols endlessly..." - not endlessly. +1 $\endgroup$ – TT_ Jan 24 '18 at 23:14
2
$\begingroup$

I find discrepancy in the first statement of your's - there are 7 vertices in both the graphs then you have 6 edges in both the graphs. This basic condition if true then it can further be proved that the two given simple graphs can be isomorphic or not? - depending onto the result.

Next you made mappings from G(1st graph) to H(2nd graph)- which is correct but then also - you cannot say that these are isomorphic. What you need to do is - you need to make an adjacent matrix adj(G) and another adjacent matrix adj(h) where adj(h) will be as per the mappings you've done for the graph H using G!

if adj(G) and adj(h) are same, then you say that these graphs are isomorphic otherwise they aren't!

Hope you get it!

$\endgroup$

protected by user99914 Jan 9 '18 at 18:07

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.