http://prntscr.com/8h7e70
Isomorphism, two graphs g1,g2 with n vertices are said to be isomorphic, if there is a way to label the graph's vertices vi, such that an edge ViVj in G1 also exists as edge ViVj in G2

- dan815

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- dan815

|dw:1442453583161:dw|

- dan815

edges of g1 are 12,15,23,34,45
and the same edges are present in g2

- dan815

i was thinking its some case like, taking a look at all the 3 degree vertices, because that subgraph also has to be isomorphic

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- dan815

if we can just show one of those is not isomorphic then it will save so much time

- zzr0ck3r

isomorphic to what?

- zzr0ck3r

nm I did not click the link

- dan815

okay :)

- zzr0ck3r

for sure list there verts and degree.

- zzr0ck3r

If they are dif they are not iso, if you think they are iso then you should give the iso :)

- dan815

i dont know how to go about labelling them yet to prove isomorphism or not, but i was just thinking about looking at subgraphs of all deg 2, and deg 3 and so on

- zzr0ck3r

Well, that would be good to show they are not iso, these graphs are small enough that if you just list out the verts and degrees you should be able to see the isomorphism.

- dan815

they all have degree 3

- dan815

so that that isnt simplfying anything T_T

- zzr0ck3r

yeah I am just noticing this.

- dan815

and all have 18 edges too dang

- dan815

thyeyre not gonna make it that easyh

- zzr0ck3r

I would use some algebraic graph theory then. Have you learned about adjacency matrices?

- dan815

no not yet, but i do know how to construct one, have not learned anything like what they can be really used for

- zzr0ck3r

Also the graphs are iso iff their compliments are iso...if that helps.

- zzr0ck3r

If one adjacency is jsut a permutation of the other, then they are isomorphic.

- zzr0ck3r

H, G are iso iff there is a permutation matrix P such that \(A_H=PA_GP^T\) where \(A_H,A_G\) are the respective adjacency matrices.

- zzr0ck3r

look at cycle lengths. Every graph that has all 3 degree verts contains a cycle :) maybe dif sized ones?

- zzr0ck3r

Can you find a 6 cycle for the one on the right?

- dan815

oh thats a good idea, maybe max cycles

- zzr0ck3r

nm there is a 6 cycle, but maybe some others also...

- dan815

i found a cycle with 12 vertices for the left one do u see any longer one

- zzr0ck3r

no need to find the max, if there is not a 12 in the other two then they are not isomorphic

- dan815

http://prntscr.com/8h7kyd

- dan815

yeah thats what i was hoping to find

- dan815

the right most one i cannot find one as long as 12, can you

- dan815

thanks im gonna work on this problem with this cycles stuff, this should make some progress, count the number of different cycles and stuff

- dan815

nvm i found a 12 T_T

- zzr0ck3r

same here :(

- zzr0ck3r

well like all isomorphisms, there is not a great way to go about it. I htink the matrix rout would be the fastest, but I doubt they want you to use that.

- dan815

you know i was thining, so if we just write that edge connectivity matrix

- dan815

get a compujter to compute all the different cycles from the matrix?

- zzr0ck3r

That would find if they are not iso, but that does not imply they are...

- dan815

yeah thats true, okay but can u explain this equation a bit more

- zzr0ck3r

Read about the adjacency matrix rout. I think there is a standard way to find the perm matrix if they exists.

- dan815

A_h= p A_g p^t

- zzr0ck3r

one second

- dan815

i can see when u say if there is a permutations where the matrices are equal then its true, but why is there p to the left and right and why must be the transpose

- dan815

|dw:1442455292288:dw|

- zzr0ck3r

http://math.stackexchange.com/questions/331233/showing-two-graphs-isomorphic-using-their-adjacency-matrices

- zzr0ck3r

one for columns one for rows? Something like that... I proved it last year, but I forget the detail on the proof.

- dan815

that might be a little to much for me to take in right now, how about something simpler like this

- dan815

if there is a permutation of these rows such that the 2 matrices are equal then does that mean they are isomorphic

- zzr0ck3r

for sure, because the identity matrix is a permutation matrix

- zzr0ck3r

wait, that didnt make sense what I said... lol

- zzr0ck3r

I bet they are, and it would give you the isomorphism

- dan815

okay so lets say i define my adjaceny matrix, and get a computer to permute all the possiblilities and see if there is a match, does that prove iso

- zzr0ck3r

I am not sure... Algebraic graph theory starts in 12 days :)

- dan815

oh i see why there is a P^T there, do we need to worry about he column permutations as well as row permutations too maybe

- zzr0ck3r

But if you can get one perm to look like the other, well then you can easily see the isomorphism.
They told you to prove it, so unless you have some theorem that says what you asked...I doubt it. They may want the proof via the definition of iso on finite graph.

- dan815

hmm quite interseting ill look into this more later

- zzr0ck3r

exactly.

- zzr0ck3r

as far as the column thing...

- Empty

intuition on using permutation matrices on adjacency matrices is simple, remember that matrix multiplication is associative so it doesn't matter what order you do this in. |dw:1442459245739:dw|
This corresponds to this multiplication by a permutation matrix:
\[P^TAP = B\]
where I've swapped the straight rows with the squiggly rows. Don't forget your adjacency matrix is symmetric, so it doesn't really matter. \(A=A^T\) and oh yeah one last note:
The right multiplication by P is flipping columns and left multiplication by \(P^{T}\) is flipping the rows.

- dan815

both the row and column permutation has to take place so that the edges and their correponding edges are same?

- dan815

and their corresponding vertices* are the same

- Empty

Yeah otherwise you'll get a matrix that isn't symmetric. And all adjacency matrices are symmetric so clearly this has to be fixed. This is how you fix that problem.

- dan815

|dw:1442459721077:dw|

- dan815

okay i see right there is symmetry across the diagonal

- Empty

Yeah looks good, since the bottom half of your matrix is nothing and your matrix is traceless there really are only \(\frac{n(n-1)}{2}\) entries. So you can possibly cut down on some computation time by being tricky not sure exactly how, maybe by doing something with representing your adjacency matrix as like a sum of a triangular matrix and its transpose?
\[P^TAP = P^T(T^T+T)P = P^TT^TP+P^TTP = S^T+S\] So it looks like you really only have to do your permutation matrices on the triangular matrix and that's just as good. since you can always just add the matrix to its transpose later.

- dan815

okay i see, i think i get the jist of this, ill play around with permuting matrices on matlab

- dan815

i got 1 more question, and im done with this,
How to construct 22 cycles exactly with 5 vertices,
i need to check if K5-1 is a solution, i am trying to do it combinatorically

- dan815

K5 is a completely connected graph with 5 vertices, so everything has degree 4,
and k5-1 is that graph with 1 edge missing

- dan815

any possible k5-1 graph is isomorphic if u can see that

- dan815

lets say we consider this graph without that edge missing just for the k5 case

- Empty

Well like since it's like saturated with edges isn't there only one way to make k5-1 edge?

- dan815

and yeah, thats right only one way to make a k5-1

- dan815

for a k5 graph we can have * a max cycle of 5, as any other cycle greater than 5 would mean you visited a vertex more than once

- dan815

for 5 cycles
_ , _, _, _, _
(1/2)*5!/5 divided by 5 since 1,2,3,4,5 = 2,3,4,5,1 = 3,4,5,1,2=.....
multiplied by half because you are counting the reverse direction too
123451= 154321

- dan815

for cycles of length 5
5 choose 5 * 1/2*(5-1)!
for cycles of length 4
5 Choose 4 * 1/2 * (4-1)!
for cycles of length 3
5 choose 3 * 1/2*(3-1)!
-----------------------------
For these i have to subtract the cases where vertex 2 and 5 are side by side