Are these two graphs isomorphic? Why/Why not?
$begingroup$
Are these two graphs isomorphic?
According to a GeeksforGeeks article:
These two are isomorphic:
And these two aren't isomorphic:
Manwani, C. "Graph Isomorphisms and Connectivity"
From GeeksforGeeks
https://www.geeksforgeeks.org/mathematics-graph-isomorphisms-connectivity/
According to a MathWorld article:
"Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic."
Weisstein, Eric W. "Isomorphic Graphs."
From MathWorld--A Wolfram Web Resource.
http://mathworld.wolfram.com/IsomorphicGraphs.html
The details are beyond me, but the MathWorld explanation seems to conflict with the first GeeksforGeeks example; the vertices appear the same, but they appear to be connected differently.
To add to the confusion, the same could be said for the second example. So I can't really deduce the facts.
graph-theory cryptography graph-isomorphism graph-connectivity
asked 2 hours ago
tjt263tjt263
1244
$endgroup$
|
show 2 more comments
$begingroup$
Are these two graphs isomorphic?
According to a GeeksforGeeks article:
These two are isomorphic:
And these two aren't isomorphic:
Manwani, C. "Graph Isomorphisms and Connectivity"
From GeeksforGeeks
https://www.geeksforgeeks.org/mathematics-graph-isomorphisms-connectivity/
According to a MathWorld article:
"Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic."
Weisstein, Eric W. "Isomorphic Graphs."
From MathWorld--A Wolfram Web Resource.
http://mathworld.wolfram.com/IsomorphicGraphs.html
The details are beyond me, but the MathWorld explanation seems to conflict with the first GeeksforGeeks example; the vertices appear the same, but they appear to be connected differently.
To add to the confusion, the same could be said for the second example. So I can't really deduce the facts.
graph-theory cryptography graph-isomorphism graph-connectivity
asked 2 hours ago
tjt263tjt263
1244
$endgroup$
$begingroup$
The two that are not isomorphic, are not connected in the same way
$endgroup$
– Ultradark
2 hours ago
$begingroup$
First of all, are you clear on the definition of isomorphic?
$endgroup$
– Mike
2 hours ago
$begingroup$
Any intrinsic property (like the degrees of vertices, lengths of cycles and such) are the same in isomorphic graphs. Extrinsic properties (like whether lines cross, the names of vertices and the degree of the topmost vertex) are not necessarily the same.
$endgroup$
– Arthur
2 hours ago
$begingroup$
@Ultradark None of them seem to be connected the same way though. The edges are different, otherwise they'd look identical, right? I mean, a star isn't a pentagon, and two parallel lines (=) aren't the same as a cross (×). What am I missing?
$endgroup$
– tjt263
2 hours ago
$begingroup$
@Mike I thought so, but I guess not.
$endgroup$
– tjt263
2 hours ago
|
show 2 more comments
$begingroup$
Are these two graphs isomorphic?
According to a GeeksforGeeks article:
These two are isomorphic:
And these two aren't isomorphic:
Manwani, C. "Graph Isomorphisms and Connectivity"
From GeeksforGeeks
https://www.geeksforgeeks.org/mathematics-graph-isomorphisms-connectivity/
According to a MathWorld article:
"Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic."
Weisstein, Eric W. "Isomorphic Graphs."
From MathWorld--A Wolfram Web Resource.
http://mathworld.wolfram.com/IsomorphicGraphs.html
The details are beyond me, but the MathWorld explanation seems to conflict with the first GeeksforGeeks example; the vertices appear the same, but they appear to be connected differently.
To add to the confusion, the same could be said for the second example. So I can't really deduce the facts.
graph-theory cryptography graph-isomorphism graph-connectivity
asked 2 hours ago
tjt263tjt263
1244
$endgroup$
Are these two graphs isomorphic?
According to a GeeksforGeeks article:
These two are isomorphic:
And these two aren't isomorphic:
Manwani, C. "Graph Isomorphisms and Connectivity"
From GeeksforGeeks
https://www.geeksforgeeks.org/mathematics-graph-isomorphisms-connectivity/
According to a MathWorld article:
"Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic."
Weisstein, Eric W. "Isomorphic Graphs."
From MathWorld--A Wolfram Web Resource.
http://mathworld.wolfram.com/IsomorphicGraphs.html
The details are beyond me, but the MathWorld explanation seems to conflict with the first GeeksforGeeks example; the vertices appear the same, but they appear to be connected differently.
To add to the confusion, the same could be said for the second example. So I can't really deduce the facts.
graph-theory cryptography graph-isomorphism graph-connectivity
graph-theory cryptography graph-isomorphism graph-connectivity
asked 2 hours ago
tjt263tjt263
1244
asked 2 hours ago
tjt263tjt263
1244
asked 2 hours ago
tjt263tjt263
1244
asked 2 hours ago
tjt263tjt263
1244
asked 2 hours ago
tjt263tjt263
1244
1244
$begingroup$
The two that are not isomorphic, are not connected in the same way
$endgroup$
– Ultradark
2 hours ago
$begingroup$
First of all, are you clear on the definition of isomorphic?
$endgroup$
– Mike
2 hours ago
$begingroup$
Any intrinsic property (like the degrees of vertices, lengths of cycles and such) are the same in isomorphic graphs. Extrinsic properties (like whether lines cross, the names of vertices and the degree of the topmost vertex) are not necessarily the same.
$endgroup$
– Arthur
2 hours ago
$begingroup$
@Ultradark None of them seem to be connected the same way though. The edges are different, otherwise they'd look identical, right? I mean, a star isn't a pentagon, and two parallel lines (=) aren't the same as a cross (×). What am I missing?
$endgroup$
– tjt263
2 hours ago
$begingroup$
@Mike I thought so, but I guess not.
$endgroup$
– tjt263
2 hours ago
|
show 2 more comments
$begingroup$
The two that are not isomorphic, are not connected in the same way
$endgroup$
– Ultradark
2 hours ago
$begingroup$
First of all, are you clear on the definition of isomorphic?
$endgroup$
– Mike
2 hours ago
$begingroup$
Any intrinsic property (like the degrees of vertices, lengths of cycles and such) are the same in isomorphic graphs. Extrinsic properties (like whether lines cross, the names of vertices and the degree of the topmost vertex) are not necessarily the same.
$endgroup$
– Arthur
2 hours ago
$begingroup$
@Ultradark None of them seem to be connected the same way though. The edges are different, otherwise they'd look identical, right? I mean, a star isn't a pentagon, and two parallel lines (=) aren't the same as a cross (×). What am I missing?
$endgroup$
– tjt263
2 hours ago
$begingroup$
@Mike I thought so, but I guess not.
$endgroup$
– tjt263
2 hours ago
$begingroup$
The two that are not isomorphic, are not connected in the same way
$endgroup$
– Ultradark
2 hours ago
$begingroup$
The two that are not isomorphic, are not connected in the same way
$endgroup$
– Ultradark
2 hours ago
$begingroup$
First of all, are you clear on the definition of isomorphic?
$endgroup$
– Mike
2 hours ago
$begingroup$
First of all, are you clear on the definition of isomorphic?
$endgroup$
– Mike
2 hours ago
$begingroup$
Any intrinsic property (like the degrees of vertices, lengths of cycles and such) are the same in isomorphic graphs. Extrinsic properties (like whether lines cross, the names of vertices and the degree of the topmost vertex) are not necessarily the same.
$endgroup$
– Arthur
2 hours ago
$begingroup$
Any intrinsic property (like the degrees of vertices, lengths of cycles and such) are the same in isomorphic graphs. Extrinsic properties (like whether lines cross, the names of vertices and the degree of the topmost vertex) are not necessarily the same.
$endgroup$
– Arthur
2 hours ago
$begingroup$
@Ultradark None of them seem to be connected the same way though. The edges are different, otherwise they'd look identical, right? I mean, a star isn't a pentagon, and two parallel lines (=) aren't the same as a cross (×). What am I missing?
$endgroup$
– tjt263
2 hours ago
$begingroup$
@Ultradark None of them seem to be connected the same way though. The edges are different, otherwise they'd look identical, right? I mean, a star isn't a pentagon, and two parallel lines (=) aren't the same as a cross (×). What am I missing?
$endgroup$
– tjt263
2 hours ago
$begingroup$
@Mike I thought so, but I guess not.
$endgroup$
– tjt263
2 hours ago
$begingroup$
@Mike I thought so, but I guess not.
$endgroup$
– tjt263
2 hours ago
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Both claims are correct.
Mapping $$e_1 to c_1, qquad e_2 to c_3, qquad e_3 to c_5, qquad e_4 to c_2, qquad e_5 to c_4$$ maps the edges of the left graph precisely to those of the right graph, so that map defines an isomorphism of graphs.
The right graph has cycles of length $3$ (e.g., $aefa$) but he left graph does not, so the graphs cannot be isomorphic.
answered 2 hours ago
TravisTravis
62.7k767149
$endgroup$
$begingroup$
That's even more confusing. What are the cycle lengths of the first two? 5? You say the edges match precisely, then immediately after you seem to demonstrate the contrary. I mean.. I believe you, but I still don't get it.
$endgroup$
– tjt263
2 hours ago
$begingroup$
The two sets of comments apply separately to the two pairs of graphs. The first two graphs are cyclic of order $5$, so any cycle thereof has length $5$.
$endgroup$
– Travis
1 hour ago
$begingroup$
But e2 corresponds with c2, and e3 corresponds with c3, and e4 with c4, and e5 with c5. It's about the vertices (not the edges) isn't it?
$endgroup$
– tjt263
1 hour ago
$begingroup$
There's no reason to consider that particular correspondence---it just happens that we've drawn the graph in a way that the $e_i$ are relatively positioned the same way as the $c||i$ but where we draw the vertices doesn't have anything to do with the graph itself. You should think of a graph as a pair $(V, E)$, where $V$ is a set of vertices and $E$ is a a set of edges connecting those vertices. As the first pair illustrates, there's more than one way to draw a graph.
$endgroup$
– Travis
23 mins ago
$begingroup$
In any case, whether a map between graphs is an isomorphism depends on both $V$ and $E$. For example, the graphs $K_1 cup K_1$ and $K_2$ both have two vertices, but they are not isomorphic, as $K_2$ has one component but $K_1 cup K_1$ has two.
$endgroup$
– Travis
21 mins ago
|
show 1 more comment
$begingroup$
Here's something important to keep in the back of your mind when studying graphs: the definition of a graph. There are actually a few deviations in how one can define a graph, but this one will suffice for our purposes:
A (simple) graph $G$ is an ordered pair of set $(V, E)$ (the sets of vertices and edges respectively), where $E$ consists of subsets of $V$ of cardinality $2$.
When the graph is finite (meaning $V$, and hence $E$, is a finite set), we can visually represent a graph by a diagram, assigning each point from $V$ to a distinct point in $Bbb{R}^2$ (or occasionally, $Bbb{R}^3$). If ${u, v} in E$, then we draw a path from the point representing $u$ to the point representing $v$, going through no other point representing a point in $V$.
These diagrams are what we often tell people are "graphs", but they are really just a way to represent graphs. The first diagram represents the graph:
$$G_1 = ({e_1, e_2, e_3, e_4, e_5},{{e_1, e_2},{e_2, e_3}, {e_3, e_4}, {e_4, e_5}, {e_5, e_1}}).$$
The second diagram represents the graph:
$$G_2 = ({c_1, c_4, c_2, c_5, c_3},{{c_1, c_4},{c_4, c_2}, {c_2, c_5}, {c_5, c_3}, {c_3, c_1}}).$$
(Note the leading way in which I've decided to order the elements of my sets in defining $G_2$!)
Note that, if we took the picture of $G_1$ and, say, rotated it (keeping all the labels), then that picture would represent the same graph $G_1$. Not something isomorphic to $G_1$, I mean it would have exactly the same vertex and edge sets, i.e. the graph it represents would literally be $G_1$, even though it's a new picture. You could even start moving the vertices around independently of each other (again, keeping the same labels), and the diagram will continue to represent $G_1$.
In this way, we see that there is an enormous variety of diagrams to represent exactly the same graph.
Further, it is possible for multiple graphs to produce the same diagram (except with different labels on the vertices). If you draw, for example, $G_2$, with $c_1$ in the same position as $e_1$, $c_4$ where $e_2$ was, $c_2$ where $e_3$ was, $c_5$ where $e_4$ was, and $c_3$ where $e_5$ was, and connected up the adjacent vertices with line segments, it would come out to be the same diagram as the one for $G_1$, with different labels.
In that sense, we see that $G_1$ and $G_2$ are structurally the same graph, even though they share no vertices or edges! So, pictures introduce unnecessary variety through muddling up the positions of vertices, and the set definition of graphs introduce unnecessary variety by allowing label substitutions which don't affect the actual structure of the graph. How do we talk about two graphs being the same, in a way that doesn't throw up a false negative when the points are moved or renamed?
Enter, stage left, the concept of a graph isomorphism. If we have graphs $(V_1, E_1)$ and $(V_2, E_2)$, a graph isomorphism is a bijection $f : V_1 to V_2$ with the property that ${v, w} in E_1 iff {f(v), f(w)} in E_2$. So, the function preserves adjacency.
Two graphs are "the same" when an isomorphism exists between them. The isomorphism deals purely with the set definition of graphs (and hence doesn't care how you draw them), but will still exist even if you rename the vertices. We can therefore see that $G_1$ and $G_2$ are isomorphic, with an isomorphism as described above. The way I wrote $G_1$ and $G_2$ exposes this isomorphism clearly as well.
How can you tell that the other pair of graphs is not isomorphic? I think Travis covers this well in his answer. In the graph on the right, there are three vertices, e.g. $b, c, d$, such that any pair of them is an edge in the graph, i.e. ${b, c}, {c, d}, {b, d}$ are elements of the edge set. If an isomorphism $f$ existed, there would need to be points $f(b), f(c), f(d)$ such that ${f(b), f(c)}, {f(c), f(d)}, {f(b), f(d)}$. No such points $f(b), f(c), f(d)$ exist in the first graph (via quick exhaustive search), so no isomorphism exists. This implies that there's no way to rearrange the vertices from one diagram (and change their labels) to form the other diagram.
Summary (or tl;dr):
- Graphs are defined using sets, not pictures!
- The same graph may be drawn in many ways, so don't get distracted by vertices moving!
- Isomorphisms don't care about the names of the vertices or their positions.
- To see why the first pair are isomorphic, but the second pair aren't, see Travis's answer.
answered 50 mins ago
Theo BenditTheo Bendit
19.3k12353
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3141500%2fare-these-two-graphs-isomorphic-why-why-not%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Both claims are correct.
Mapping $$e_1 to c_1, qquad e_2 to c_3, qquad e_3 to c_5, qquad e_4 to c_2, qquad e_5 to c_4$$ maps the edges of the left graph precisely to those of the right graph, so that map defines an isomorphism of graphs.
The right graph has cycles of length $3$ (e.g., $aefa$) but he left graph does not, so the graphs cannot be isomorphic.
answered 2 hours ago
TravisTravis
62.7k767149
$endgroup$
$begingroup$
That's even more confusing. What are the cycle lengths of the first two? 5? You say the edges match precisely, then immediately after you seem to demonstrate the contrary. I mean.. I believe you, but I still don't get it.
$endgroup$
– tjt263
2 hours ago
$begingroup$
The two sets of comments apply separately to the two pairs of graphs. The first two graphs are cyclic of order $5$, so any cycle thereof has length $5$.
$endgroup$
– Travis
1 hour ago
$begingroup$
But e2 corresponds with c2, and e3 corresponds with c3, and e4 with c4, and e5 with c5. It's about the vertices (not the edges) isn't it?
$endgroup$
– tjt263
1 hour ago
$begingroup$
There's no reason to consider that particular correspondence---it just happens that we've drawn the graph in a way that the $e_i$ are relatively positioned the same way as the $c||i$ but where we draw the vertices doesn't have anything to do with the graph itself. You should think of a graph as a pair $(V, E)$, where $V$ is a set of vertices and $E$ is a a set of edges connecting those vertices. As the first pair illustrates, there's more than one way to draw a graph.
$endgroup$
– Travis
23 mins ago
$begingroup$
In any case, whether a map between graphs is an isomorphism depends on both $V$ and $E$. For example, the graphs $K_1 cup K_1$ and $K_2$ both have two vertices, but they are not isomorphic, as $K_2$ has one component but $K_1 cup K_1$ has two.
$endgroup$
– Travis
21 mins ago
|
show 1 more comment
$begingroup$
Both claims are correct.
Mapping $$e_1 to c_1, qquad e_2 to c_3, qquad e_3 to c_5, qquad e_4 to c_2, qquad e_5 to c_4$$ maps the edges of the left graph precisely to those of the right graph, so that map defines an isomorphism of graphs.
The right graph has cycles of length $3$ (e.g., $aefa$) but he left graph does not, so the graphs cannot be isomorphic.
answered 2 hours ago
TravisTravis
62.7k767149
$endgroup$
$begingroup$
That's even more confusing. What are the cycle lengths of the first two? 5? You say the edges match precisely, then immediately after you seem to demonstrate the contrary. I mean.. I believe you, but I still don't get it.
$endgroup$
– tjt263
2 hours ago
$begingroup$
The two sets of comments apply separately to the two pairs of graphs. The first two graphs are cyclic of order $5$, so any cycle thereof has length $5$.
$endgroup$
– Travis
1 hour ago
$begingroup$
But e2 corresponds with c2, and e3 corresponds with c3, and e4 with c4, and e5 with c5. It's about the vertices (not the edges) isn't it?
$endgroup$
– tjt263
1 hour ago
$begingroup$
There's no reason to consider that particular correspondence---it just happens that we've drawn the graph in a way that the $e_i$ are relatively positioned the same way as the $c||i$ but where we draw the vertices doesn't have anything to do with the graph itself. You should think of a graph as a pair $(V, E)$, where $V$ is a set of vertices and $E$ is a a set of edges connecting those vertices. As the first pair illustrates, there's more than one way to draw a graph.
$endgroup$
– Travis
23 mins ago
$begingroup$
In any case, whether a map between graphs is an isomorphism depends on both $V$ and $E$. For example, the graphs $K_1 cup K_1$ and $K_2$ both have two vertices, but they are not isomorphic, as $K_2$ has one component but $K_1 cup K_1$ has two.
$endgroup$
– Travis
21 mins ago
|
show 1 more comment
$begingroup$
Both claims are correct.
Mapping $$e_1 to c_1, qquad e_2 to c_3, qquad e_3 to c_5, qquad e_4 to c_2, qquad e_5 to c_4$$ maps the edges of the left graph precisely to those of the right graph, so that map defines an isomorphism of graphs.
The right graph has cycles of length $3$ (e.g., $aefa$) but he left graph does not, so the graphs cannot be isomorphic.
answered 2 hours ago
TravisTravis
62.7k767149
$endgroup$
Both claims are correct.
Mapping $$e_1 to c_1, qquad e_2 to c_3, qquad e_3 to c_5, qquad e_4 to c_2, qquad e_5 to c_4$$ maps the edges of the left graph precisely to those of the right graph, so that map defines an isomorphism of graphs.
The right graph has cycles of length $3$ (e.g., $aefa$) but he left graph does not, so the graphs cannot be isomorphic.
answered 2 hours ago
TravisTravis
62.7k767149
answered 2 hours ago
TravisTravis
62.7k767149
answered 2 hours ago
TravisTravis
62.7k767149
answered 2 hours ago
TravisTravis
62.7k767149
62.7k767149
$begingroup$
That's even more confusing. What are the cycle lengths of the first two? 5? You say the edges match precisely, then immediately after you seem to demonstrate the contrary. I mean.. I believe you, but I still don't get it.
$endgroup$
– tjt263
2 hours ago
$begingroup$
The two sets of comments apply separately to the two pairs of graphs. The first two graphs are cyclic of order $5$, so any cycle thereof has length $5$.
$endgroup$
– Travis
1 hour ago
$begingroup$
But e2 corresponds with c2, and e3 corresponds with c3, and e4 with c4, and e5 with c5. It's about the vertices (not the edges) isn't it?
$endgroup$
– tjt263
1 hour ago
$begingroup$
There's no reason to consider that particular correspondence---it just happens that we've drawn the graph in a way that the $e_i$ are relatively positioned the same way as the $c||i$ but where we draw the vertices doesn't have anything to do with the graph itself. You should think of a graph as a pair $(V, E)$, where $V$ is a set of vertices and $E$ is a a set of edges connecting those vertices. As the first pair illustrates, there's more than one way to draw a graph.
$endgroup$
– Travis
23 mins ago
$begingroup$
In any case, whether a map between graphs is an isomorphism depends on both $V$ and $E$. For example, the graphs $K_1 cup K_1$ and $K_2$ both have two vertices, but they are not isomorphic, as $K_2$ has one component but $K_1 cup K_1$ has two.
$endgroup$
– Travis
21 mins ago
|
show 1 more comment
$begingroup$
That's even more confusing. What are the cycle lengths of the first two? 5? You say the edges match precisely, then immediately after you seem to demonstrate the contrary. I mean.. I believe you, but I still don't get it.
$endgroup$
– tjt263
2 hours ago
$begingroup$
The two sets of comments apply separately to the two pairs of graphs. The first two graphs are cyclic of order $5$, so any cycle thereof has length $5$.
$endgroup$
– Travis
1 hour ago
$begingroup$
But e2 corresponds with c2, and e3 corresponds with c3, and e4 with c4, and e5 with c5. It's about the vertices (not the edges) isn't it?
$endgroup$
– tjt263
1 hour ago
$begingroup$
There's no reason to consider that particular correspondence---it just happens that we've drawn the graph in a way that the $e_i$ are relatively positioned the same way as the $c||i$ but where we draw the vertices doesn't have anything to do with the graph itself. You should think of a graph as a pair $(V, E)$, where $V$ is a set of vertices and $E$ is a a set of edges connecting those vertices. As the first pair illustrates, there's more than one way to draw a graph.
$endgroup$
– Travis
23 mins ago
$begingroup$
In any case, whether a map between graphs is an isomorphism depends on both $V$ and $E$. For example, the graphs $K_1 cup K_1$ and $K_2$ both have two vertices, but they are not isomorphic, as $K_2$ has one component but $K_1 cup K_1$ has two.
$endgroup$
– Travis
21 mins ago
$begingroup$
That's even more confusing. What are the cycle lengths of the first two? 5? You say the edges match precisely, then immediately after you seem to demonstrate the contrary. I mean.. I believe you, but I still don't get it.
$endgroup$
– tjt263
2 hours ago
$begingroup$
That's even more confusing. What are the cycle lengths of the first two? 5? You say the edges match precisely, then immediately after you seem to demonstrate the contrary. I mean.. I believe you, but I still don't get it.
$endgroup$
– tjt263
2 hours ago
$begingroup$
The two sets of comments apply separately to the two pairs of graphs. The first two graphs are cyclic of order $5$, so any cycle thereof has length $5$.
$endgroup$
– Travis
1 hour ago
$begingroup$
The two sets of comments apply separately to the two pairs of graphs. The first two graphs are cyclic of order $5$, so any cycle thereof has length $5$.
$endgroup$
– Travis
1 hour ago
$begingroup$
But e2 corresponds with c2, and e3 corresponds with c3, and e4 with c4, and e5 with c5. It's about the vertices (not the edges) isn't it?
$endgroup$
– tjt263
1 hour ago
$begingroup$
But e2 corresponds with c2, and e3 corresponds with c3, and e4 with c4, and e5 with c5. It's about the vertices (not the edges) isn't it?
$endgroup$
– tjt263
1 hour ago
$begingroup$
There's no reason to consider that particular correspondence---it just happens that we've drawn the graph in a way that the $e_i$ are relatively positioned the same way as the $c||i$ but where we draw the vertices doesn't have anything to do with the graph itself. You should think of a graph as a pair $(V, E)$, where $V$ is a set of vertices and $E$ is a a set of edges connecting those vertices. As the first pair illustrates, there's more than one way to draw a graph.
$endgroup$
– Travis
23 mins ago
$begingroup$
There's no reason to consider that particular correspondence---it just happens that we've drawn the graph in a way that the $e_i$ are relatively positioned the same way as the $c||i$ but where we draw the vertices doesn't have anything to do with the graph itself. You should think of a graph as a pair $(V, E)$, where $V$ is a set of vertices and $E$ is a a set of edges connecting those vertices. As the first pair illustrates, there's more than one way to draw a graph.
$endgroup$
– Travis
23 mins ago
$begingroup$
In any case, whether a map between graphs is an isomorphism depends on both $V$ and $E$. For example, the graphs $K_1 cup K_1$ and $K_2$ both have two vertices, but they are not isomorphic, as $K_2$ has one component but $K_1 cup K_1$ has two.
$endgroup$
– Travis
21 mins ago
$begingroup$
In any case, whether a map between graphs is an isomorphism depends on both $V$ and $E$. For example, the graphs $K_1 cup K_1$ and $K_2$ both have two vertices, but they are not isomorphic, as $K_2$ has one component but $K_1 cup K_1$ has two.
$endgroup$
– Travis
21 mins ago
|
show 1 more comment
$begingroup$
Here's something important to keep in the back of your mind when studying graphs: the definition of a graph. There are actually a few deviations in how one can define a graph, but this one will suffice for our purposes:
A (simple) graph $G$ is an ordered pair of set $(V, E)$ (the sets of vertices and edges respectively), where $E$ consists of subsets of $V$ of cardinality $2$.
When the graph is finite (meaning $V$, and hence $E$, is a finite set), we can visually represent a graph by a diagram, assigning each point from $V$ to a distinct point in $Bbb{R}^2$ (or occasionally, $Bbb{R}^3$). If ${u, v} in E$, then we draw a path from the point representing $u$ to the point representing $v$, going through no other point representing a point in $V$.
These diagrams are what we often tell people are "graphs", but they are really just a way to represent graphs. The first diagram represents the graph:
$$G_1 = ({e_1, e_2, e_3, e_4, e_5},{{e_1, e_2},{e_2, e_3}, {e_3, e_4}, {e_4, e_5}, {e_5, e_1}}).$$
The second diagram represents the graph:
$$G_2 = ({c_1, c_4, c_2, c_5, c_3},{{c_1, c_4},{c_4, c_2}, {c_2, c_5}, {c_5, c_3}, {c_3, c_1}}).$$
(Note the leading way in which I've decided to order the elements of my sets in defining $G_2$!)
Note that, if we took the picture of $G_1$ and, say, rotated it (keeping all the labels), then that picture would represent the same graph $G_1$. Not something isomorphic to $G_1$, I mean it would have exactly the same vertex and edge sets, i.e. the graph it represents would literally be $G_1$, even though it's a new picture. You could even start moving the vertices around independently of each other (again, keeping the same labels), and the diagram will continue to represent $G_1$.
In this way, we see that there is an enormous variety of diagrams to represent exactly the same graph.
Further, it is possible for multiple graphs to produce the same diagram (except with different labels on the vertices). If you draw, for example, $G_2$, with $c_1$ in the same position as $e_1$, $c_4$ where $e_2$ was, $c_2$ where $e_3$ was, $c_5$ where $e_4$ was, and $c_3$ where $e_5$ was, and connected up the adjacent vertices with line segments, it would come out to be the same diagram as the one for $G_1$, with different labels.
In that sense, we see that $G_1$ and $G_2$ are structurally the same graph, even though they share no vertices or edges! So, pictures introduce unnecessary variety through muddling up the positions of vertices, and the set definition of graphs introduce unnecessary variety by allowing label substitutions which don't affect the actual structure of the graph. How do we talk about two graphs being the same, in a way that doesn't throw up a false negative when the points are moved or renamed?
Enter, stage left, the concept of a graph isomorphism. If we have graphs $(V_1, E_1)$ and $(V_2, E_2)$, a graph isomorphism is a bijection $f : V_1 to V_2$ with the property that ${v, w} in E_1 iff {f(v), f(w)} in E_2$. So, the function preserves adjacency.
Two graphs are "the same" when an isomorphism exists between them. The isomorphism deals purely with the set definition of graphs (and hence doesn't care how you draw them), but will still exist even if you rename the vertices. We can therefore see that $G_1$ and $G_2$ are isomorphic, with an isomorphism as described above. The way I wrote $G_1$ and $G_2$ exposes this isomorphism clearly as well.
How can you tell that the other pair of graphs is not isomorphic? I think Travis covers this well in his answer. In the graph on the right, there are three vertices, e.g. $b, c, d$, such that any pair of them is an edge in the graph, i.e. ${b, c}, {c, d}, {b, d}$ are elements of the edge set. If an isomorphism $f$ existed, there would need to be points $f(b), f(c), f(d)$ such that ${f(b), f(c)}, {f(c), f(d)}, {f(b), f(d)}$. No such points $f(b), f(c), f(d)$ exist in the first graph (via quick exhaustive search), so no isomorphism exists. This implies that there's no way to rearrange the vertices from one diagram (and change their labels) to form the other diagram.
Summary (or tl;dr):
- Graphs are defined using sets, not pictures!
- The same graph may be drawn in many ways, so don't get distracted by vertices moving!
- Isomorphisms don't care about the names of the vertices or their positions.
- To see why the first pair are isomorphic, but the second pair aren't, see Travis's answer.
answered 50 mins ago
Theo BenditTheo Bendit
19.3k12353
$endgroup$
add a comment |
$begingroup$
Here's something important to keep in the back of your mind when studying graphs: the definition of a graph. There are actually a few deviations in how one can define a graph, but this one will suffice for our purposes:
A (simple) graph $G$ is an ordered pair of set $(V, E)$ (the sets of vertices and edges respectively), where $E$ consists of subsets of $V$ of cardinality $2$.
When the graph is finite (meaning $V$, and hence $E$, is a finite set), we can visually represent a graph by a diagram, assigning each point from $V$ to a distinct point in $Bbb{R}^2$ (or occasionally, $Bbb{R}^3$). If ${u, v} in E$, then we draw a path from the point representing $u$ to the point representing $v$, going through no other point representing a point in $V$.
These diagrams are what we often tell people are "graphs", but they are really just a way to represent graphs. The first diagram represents the graph:
$$G_1 = ({e_1, e_2, e_3, e_4, e_5},{{e_1, e_2},{e_2, e_3}, {e_3, e_4}, {e_4, e_5}, {e_5, e_1}}).$$
The second diagram represents the graph:
$$G_2 = ({c_1, c_4, c_2, c_5, c_3},{{c_1, c_4},{c_4, c_2}, {c_2, c_5}, {c_5, c_3}, {c_3, c_1}}).$$
(Note the leading way in which I've decided to order the elements of my sets in defining $G_2$!)
Note that, if we took the picture of $G_1$ and, say, rotated it (keeping all the labels), then that picture would represent the same graph $G_1$. Not something isomorphic to $G_1$, I mean it would have exactly the same vertex and edge sets, i.e. the graph it represents would literally be $G_1$, even though it's a new picture. You could even start moving the vertices around independently of each other (again, keeping the same labels), and the diagram will continue to represent $G_1$.
In this way, we see that there is an enormous variety of diagrams to represent exactly the same graph.
Further, it is possible for multiple graphs to produce the same diagram (except with different labels on the vertices). If you draw, for example, $G_2$, with $c_1$ in the same position as $e_1$, $c_4$ where $e_2$ was, $c_2$ where $e_3$ was, $c_5$ where $e_4$ was, and $c_3$ where $e_5$ was, and connected up the adjacent vertices with line segments, it would come out to be the same diagram as the one for $G_1$, with different labels.
In that sense, we see that $G_1$ and $G_2$ are structurally the same graph, even though they share no vertices or edges! So, pictures introduce unnecessary variety through muddling up the positions of vertices, and the set definition of graphs introduce unnecessary variety by allowing label substitutions which don't affect the actual structure of the graph. How do we talk about two graphs being the same, in a way that doesn't throw up a false negative when the points are moved or renamed?
Enter, stage left, the concept of a graph isomorphism. If we have graphs $(V_1, E_1)$ and $(V_2, E_2)$, a graph isomorphism is a bijection $f : V_1 to V_2$ with the property that ${v, w} in E_1 iff {f(v), f(w)} in E_2$. So, the function preserves adjacency.
Two graphs are "the same" when an isomorphism exists between them. The isomorphism deals purely with the set definition of graphs (and hence doesn't care how you draw them), but will still exist even if you rename the vertices. We can therefore see that $G_1$ and $G_2$ are isomorphic, with an isomorphism as described above. The way I wrote $G_1$ and $G_2$ exposes this isomorphism clearly as well.
How can you tell that the other pair of graphs is not isomorphic? I think Travis covers this well in his answer. In the graph on the right, there are three vertices, e.g. $b, c, d$, such that any pair of them is an edge in the graph, i.e. ${b, c}, {c, d}, {b, d}$ are elements of the edge set. If an isomorphism $f$ existed, there would need to be points $f(b), f(c), f(d)$ such that ${f(b), f(c)}, {f(c), f(d)}, {f(b), f(d)}$. No such points $f(b), f(c), f(d)$ exist in the first graph (via quick exhaustive search), so no isomorphism exists. This implies that there's no way to rearrange the vertices from one diagram (and change their labels) to form the other diagram.
Summary (or tl;dr):
- Graphs are defined using sets, not pictures!
- The same graph may be drawn in many ways, so don't get distracted by vertices moving!
- Isomorphisms don't care about the names of the vertices or their positions.
- To see why the first pair are isomorphic, but the second pair aren't, see Travis's answer.
answered 50 mins ago
Theo BenditTheo Bendit
19.3k12353
$endgroup$
add a comment |
$begingroup$
Here's something important to keep in the back of your mind when studying graphs: the definition of a graph. There are actually a few deviations in how one can define a graph, but this one will suffice for our purposes:
A (simple) graph $G$ is an ordered pair of set $(V, E)$ (the sets of vertices and edges respectively), where $E$ consists of subsets of $V$ of cardinality $2$.
When the graph is finite (meaning $V$, and hence $E$, is a finite set), we can visually represent a graph by a diagram, assigning each point from $V$ to a distinct point in $Bbb{R}^2$ (or occasionally, $Bbb{R}^3$). If ${u, v} in E$, then we draw a path from the point representing $u$ to the point representing $v$, going through no other point representing a point in $V$.
These diagrams are what we often tell people are "graphs", but they are really just a way to represent graphs. The first diagram represents the graph:
$$G_1 = ({e_1, e_2, e_3, e_4, e_5},{{e_1, e_2},{e_2, e_3}, {e_3, e_4}, {e_4, e_5}, {e_5, e_1}}).$$
The second diagram represents the graph:
$$G_2 = ({c_1, c_4, c_2, c_5, c_3},{{c_1, c_4},{c_4, c_2}, {c_2, c_5}, {c_5, c_3}, {c_3, c_1}}).$$
(Note the leading way in which I've decided to order the elements of my sets in defining $G_2$!)
Note that, if we took the picture of $G_1$ and, say, rotated it (keeping all the labels), then that picture would represent the same graph $G_1$. Not something isomorphic to $G_1$, I mean it would have exactly the same vertex and edge sets, i.e. the graph it represents would literally be $G_1$, even though it's a new picture. You could even start moving the vertices around independently of each other (again, keeping the same labels), and the diagram will continue to represent $G_1$.
In this way, we see that there is an enormous variety of diagrams to represent exactly the same graph.
Further, it is possible for multiple graphs to produce the same diagram (except with different labels on the vertices). If you draw, for example, $G_2$, with $c_1$ in the same position as $e_1$, $c_4$ where $e_2$ was, $c_2$ where $e_3$ was, $c_5$ where $e_4$ was, and $c_3$ where $e_5$ was, and connected up the adjacent vertices with line segments, it would come out to be the same diagram as the one for $G_1$, with different labels.
In that sense, we see that $G_1$ and $G_2$ are structurally the same graph, even though they share no vertices or edges! So, pictures introduce unnecessary variety through muddling up the positions of vertices, and the set definition of graphs introduce unnecessary variety by allowing label substitutions which don't affect the actual structure of the graph. How do we talk about two graphs being the same, in a way that doesn't throw up a false negative when the points are moved or renamed?
Enter, stage left, the concept of a graph isomorphism. If we have graphs $(V_1, E_1)$ and $(V_2, E_2)$, a graph isomorphism is a bijection $f : V_1 to V_2$ with the property that ${v, w} in E_1 iff {f(v), f(w)} in E_2$. So, the function preserves adjacency.
Two graphs are "the same" when an isomorphism exists between them. The isomorphism deals purely with the set definition of graphs (and hence doesn't care how you draw them), but will still exist even if you rename the vertices. We can therefore see that $G_1$ and $G_2$ are isomorphic, with an isomorphism as described above. The way I wrote $G_1$ and $G_2$ exposes this isomorphism clearly as well.
How can you tell that the other pair of graphs is not isomorphic? I think Travis covers this well in his answer. In the graph on the right, there are three vertices, e.g. $b, c, d$, such that any pair of them is an edge in the graph, i.e. ${b, c}, {c, d}, {b, d}$ are elements of the edge set. If an isomorphism $f$ existed, there would need to be points $f(b), f(c), f(d)$ such that ${f(b), f(c)}, {f(c), f(d)}, {f(b), f(d)}$. No such points $f(b), f(c), f(d)$ exist in the first graph (via quick exhaustive search), so no isomorphism exists. This implies that there's no way to rearrange the vertices from one diagram (and change their labels) to form the other diagram.
Summary (or tl;dr):
- Graphs are defined using sets, not pictures!
- The same graph may be drawn in many ways, so don't get distracted by vertices moving!
- Isomorphisms don't care about the names of the vertices or their positions.
- To see why the first pair are isomorphic, but the second pair aren't, see Travis's answer.
answered 50 mins ago
Theo BenditTheo Bendit
19.3k12353
$endgroup$
Here's something important to keep in the back of your mind when studying graphs: the definition of a graph. There are actually a few deviations in how one can define a graph, but this one will suffice for our purposes:
A (simple) graph $G$ is an ordered pair of set $(V, E)$ (the sets of vertices and edges respectively), where $E$ consists of subsets of $V$ of cardinality $2$.
When the graph is finite (meaning $V$, and hence $E$, is a finite set), we can visually represent a graph by a diagram, assigning each point from $V$ to a distinct point in $Bbb{R}^2$ (or occasionally, $Bbb{R}^3$). If ${u, v} in E$, then we draw a path from the point representing $u$ to the point representing $v$, going through no other point representing a point in $V$.
These diagrams are what we often tell people are "graphs", but they are really just a way to represent graphs. The first diagram represents the graph:
$$G_1 = ({e_1, e_2, e_3, e_4, e_5},{{e_1, e_2},{e_2, e_3}, {e_3, e_4}, {e_4, e_5}, {e_5, e_1}}).$$
The second diagram represents the graph:
$$G_2 = ({c_1, c_4, c_2, c_5, c_3},{{c_1, c_4},{c_4, c_2}, {c_2, c_5}, {c_5, c_3}, {c_3, c_1}}).$$
(Note the leading way in which I've decided to order the elements of my sets in defining $G_2$!)
Note that, if we took the picture of $G_1$ and, say, rotated it (keeping all the labels), then that picture would represent the same graph $G_1$. Not something isomorphic to $G_1$, I mean it would have exactly the same vertex and edge sets, i.e. the graph it represents would literally be $G_1$, even though it's a new picture. You could even start moving the vertices around independently of each other (again, keeping the same labels), and the diagram will continue to represent $G_1$.
In this way, we see that there is an enormous variety of diagrams to represent exactly the same graph.
Further, it is possible for multiple graphs to produce the same diagram (except with different labels on the vertices). If you draw, for example, $G_2$, with $c_1$ in the same position as $e_1$, $c_4$ where $e_2$ was, $c_2$ where $e_3$ was, $c_5$ where $e_4$ was, and $c_3$ where $e_5$ was, and connected up the adjacent vertices with line segments, it would come out to be the same diagram as the one for $G_1$, with different labels.
In that sense, we see that $G_1$ and $G_2$ are structurally the same graph, even though they share no vertices or edges! So, pictures introduce unnecessary variety through muddling up the positions of vertices, and the set definition of graphs introduce unnecessary variety by allowing label substitutions which don't affect the actual structure of the graph. How do we talk about two graphs being the same, in a way that doesn't throw up a false negative when the points are moved or renamed?
Enter, stage left, the concept of a graph isomorphism. If we have graphs $(V_1, E_1)$ and $(V_2, E_2)$, a graph isomorphism is a bijection $f : V_1 to V_2$ with the property that ${v, w} in E_1 iff {f(v), f(w)} in E_2$. So, the function preserves adjacency.
Two graphs are "the same" when an isomorphism exists between them. The isomorphism deals purely with the set definition of graphs (and hence doesn't care how you draw them), but will still exist even if you rename the vertices. We can therefore see that $G_1$ and $G_2$ are isomorphic, with an isomorphism as described above. The way I wrote $G_1$ and $G_2$ exposes this isomorphism clearly as well.
How can you tell that the other pair of graphs is not isomorphic? I think Travis covers this well in his answer. In the graph on the right, there are three vertices, e.g. $b, c, d$, such that any pair of them is an edge in the graph, i.e. ${b, c}, {c, d}, {b, d}$ are elements of the edge set. If an isomorphism $f$ existed, there would need to be points $f(b), f(c), f(d)$ such that ${f(b), f(c)}, {f(c), f(d)}, {f(b), f(d)}$. No such points $f(b), f(c), f(d)$ exist in the first graph (via quick exhaustive search), so no isomorphism exists. This implies that there's no way to rearrange the vertices from one diagram (and change their labels) to form the other diagram.
Summary (or tl;dr):
- Graphs are defined using sets, not pictures!
- The same graph may be drawn in many ways, so don't get distracted by vertices moving!
- Isomorphisms don't care about the names of the vertices or their positions.
- To see why the first pair are isomorphic, but the second pair aren't, see Travis's answer.
answered 50 mins ago
Theo BenditTheo Bendit
19.3k12353
answered 50 mins ago
Theo BenditTheo Bendit
19.3k12353
answered 50 mins ago
Theo BenditTheo Bendit
19.3k12353
answered 50 mins ago
Theo BenditTheo Bendit
19.3k12353
19.3k12353
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3141500%2fare-these-two-graphs-isomorphic-why-why-not%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
The two that are not isomorphic, are not connected in the same way
$endgroup$
– Ultradark
2 hours ago
$begingroup$
First of all, are you clear on the definition of isomorphic?
$endgroup$
– Mike
2 hours ago
$begingroup$
Any intrinsic property (like the degrees of vertices, lengths of cycles and such) are the same in isomorphic graphs. Extrinsic properties (like whether lines cross, the names of vertices and the degree of the topmost vertex) are not necessarily the same.
$endgroup$
– Arthur
2 hours ago
$begingroup$
@Ultradark None of them seem to be connected the same way though. The edges are different, otherwise they'd look identical, right? I mean, a star isn't a pentagon, and two parallel lines (=) aren't the same as a cross (×). What am I missing?
$endgroup$
– tjt263
2 hours ago
$begingroup$
@Mike I thought so, but I guess not.
$endgroup$
– tjt263
2 hours ago