Prove that a graph is isomorphic with its line graph The 2019 Stack Overflow Developer Survey Results Are In Unicorn Meta Zoo #1: Why another podcast? Announcing the arrival of Valued Associate #679: Cesar ManaraGenerating non-isomorphic graph by adding two edges to a fixed graphConstructing a 3-regular graph with no 3-cyclesName for two cycles that share edges or are connected by a path?A directed graph and existence of vertex of finite degreeCentral limit theorem for perfect matching countsFinding the maximum weighted path in a directed cyclic weighted graph with probabilities on edgesA graph is distance transitive iff it is vertex transitiveDirected Cayley Graph With No Hamilton CyclesHamiltonian cycle - Collection of disjointed Hamiltonian cyclesfactorisations of vertex transitive graphs
"... to apply for a visa" or "... and applied for a visa"?
Single author papers against my advisor's will?
Why can't wing-mounted spoilers be used to steepen approaches?
Does Parliament hold absolute power in the UK?
Why are PDP-7-style microprogrammed instructions out of vogue?
Why doesn't shell automatically fix "useless use of cat"?
Do ℕ, mathbbN, BbbN, symbbN effectively differ, and is there a "canonical" specification of the naturals?
Homework question about an engine pulling a train
Identify 80s or 90s comics with ripped creatures (not dwarves)
Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?
Is this wall load bearing? Blueprints and photos attached
Would an alien lifeform be able to achieve space travel if lacking in vision?
Circular reasoning in L'Hopital's rule
US Healthcare consultation for visitors
Huge performance difference of the command find with and without using %M option to show permissions
should truth entail possible truth
What do I do when my TA workload is more than expected?
Are spiders unable to hurt humans, especially very small spiders?
A phrase ”follow into" in a context
Did the new image of black hole confirm the general theory of relativity?
What is the padding with red substance inside of steak packaging?
Store Dynamic-accessible hidden metadata in a cell
Make it rain characters
How do spell lists change if the party levels up without taking a long rest?
Prove that a graph is isomorphic with its line graph
The 2019 Stack Overflow Developer Survey Results Are In
Unicorn Meta Zoo #1: Why another podcast?
Announcing the arrival of Valued Associate #679: Cesar ManaraGenerating non-isomorphic graph by adding two edges to a fixed graphConstructing a 3-regular graph with no 3-cyclesName for two cycles that share edges or are connected by a path?A directed graph and existence of vertex of finite degreeCentral limit theorem for perfect matching countsFinding the maximum weighted path in a directed cyclic weighted graph with probabilities on edgesA graph is distance transitive iff it is vertex transitiveDirected Cayley Graph With No Hamilton CyclesHamiltonian cycle - Collection of disjointed Hamiltonian cyclesfactorisations of vertex transitive graphs
$begingroup$
$Gcong L(G)$ iff there is a $rin mathbbN$ such that $G=C_i_1+C_i_2+...+C_i_r$ , $i_jge3$ and $1le jleq r$; equivalently, iff for some positive integer $r$, the graph $G$ is a collection of $r$ vertex-disjoint cycles $C_i_1, C_i_2, ldots, C_i_r$.
I think I have to use that $C_r, rge3$ is transitive this means that there is an automorpism $Aut(C_r): s(x)=y$, $x,y in V(C_r)$
But I'm not really sure how, any ideas on that?
graph-theory
edited Mar 24 at 19:09
Mike
4,631512
asked Mar 24 at 17:03
VakiPitsiVakiPitsi
31719
$endgroup$
add a comment |
$begingroup$
$Gcong L(G)$ iff there is a $rin mathbbN$ such that $G=C_i_1+C_i_2+...+C_i_r$ , $i_jge3$ and $1le jleq r$; equivalently, iff for some positive integer $r$, the graph $G$ is a collection of $r$ vertex-disjoint cycles $C_i_1, C_i_2, ldots, C_i_r$.
I think I have to use that $C_r, rge3$ is transitive this means that there is an automorpism $Aut(C_r): s(x)=y$, $x,y in V(C_r)$
But I'm not really sure how, any ideas on that?
graph-theory
edited Mar 24 at 19:09
Mike
4,631512
asked Mar 24 at 17:03
VakiPitsiVakiPitsi
31719
$endgroup$
$begingroup$
You may want to explain your notation further. What is $C_i$?
$endgroup$
– Mike
Mar 24 at 17:38
$begingroup$
It's the standard notation for the cycle graph with i vertices
$endgroup$
– VakiPitsi
Mar 24 at 17:46
1
$begingroup$
Thank you for the clarification, I see it now, I think I had misread the question. But [and I am not meaning to nitpick here] it would also be helpful to note in the statement of your problem that the $C_i$s are mutually vertex-disjoint as opposed to merely edge-disjoint
$endgroup$
– Mike
Mar 24 at 19:04
$begingroup$
...as the + notation in graph theory can be ambiguous!
$endgroup$
– Mike
Mar 24 at 19:17
$begingroup$
Thank you Mike for observation, I'm not very familiar with graph theory so I'm not aware of such misconseptions
$endgroup$
– VakiPitsi
Mar 25 at 14:33
add a comment |
$begingroup$
$Gcong L(G)$ iff there is a $rin mathbbN$ such that $G=C_i_1+C_i_2+...+C_i_r$ , $i_jge3$ and $1le jleq r$; equivalently, iff for some positive integer $r$, the graph $G$ is a collection of $r$ vertex-disjoint cycles $C_i_1, C_i_2, ldots, C_i_r$.
I think I have to use that $C_r, rge3$ is transitive this means that there is an automorpism $Aut(C_r): s(x)=y$, $x,y in V(C_r)$
But I'm not really sure how, any ideas on that?
graph-theory
edited Mar 24 at 19:09
Mike
4,631512
asked Mar 24 at 17:03
VakiPitsiVakiPitsi
31719
$endgroup$
$Gcong L(G)$ iff there is a $rin mathbbN$ such that $G=C_i_1+C_i_2+...+C_i_r$ , $i_jge3$ and $1le jleq r$; equivalently, iff for some positive integer $r$, the graph $G$ is a collection of $r$ vertex-disjoint cycles $C_i_1, C_i_2, ldots, C_i_r$.
I think I have to use that $C_r, rge3$ is transitive this means that there is an automorpism $Aut(C_r): s(x)=y$, $x,y in V(C_r)$
But I'm not really sure how, any ideas on that?
graph-theory
graph-theory
edited Mar 24 at 19:09
Mike
4,631512
asked Mar 24 at 17:03
VakiPitsiVakiPitsi
31719
edited Mar 24 at 19:09
Mike
4,631512
asked Mar 24 at 17:03
VakiPitsiVakiPitsi
31719
edited Mar 24 at 19:09
Mike
4,631512
edited Mar 24 at 19:09
Mike
4,631512
edited Mar 24 at 19:09
Mike
4,631512
4,631512
asked Mar 24 at 17:03
VakiPitsiVakiPitsi
31719
asked Mar 24 at 17:03
VakiPitsiVakiPitsi
31719
asked Mar 24 at 17:03
VakiPitsiVakiPitsi
31719
31719
$begingroup$
You may want to explain your notation further. What is $C_i$?
$endgroup$
– Mike
Mar 24 at 17:38
$begingroup$
It's the standard notation for the cycle graph with i vertices
$endgroup$
– VakiPitsi
Mar 24 at 17:46
1
$begingroup$
Thank you for the clarification, I see it now, I think I had misread the question. But [and I am not meaning to nitpick here] it would also be helpful to note in the statement of your problem that the $C_i$s are mutually vertex-disjoint as opposed to merely edge-disjoint
$endgroup$
– Mike
Mar 24 at 19:04
$begingroup$
...as the + notation in graph theory can be ambiguous!
$endgroup$
– Mike
Mar 24 at 19:17
$begingroup$
Thank you Mike for observation, I'm not very familiar with graph theory so I'm not aware of such misconseptions
$endgroup$
– VakiPitsi
Mar 25 at 14:33
add a comment |
$begingroup$
You may want to explain your notation further. What is $C_i$?
$endgroup$
– Mike
Mar 24 at 17:38
$begingroup$
It's the standard notation for the cycle graph with i vertices
$endgroup$
– VakiPitsi
Mar 24 at 17:46
1
$begingroup$
Thank you for the clarification, I see it now, I think I had misread the question. But [and I am not meaning to nitpick here] it would also be helpful to note in the statement of your problem that the $C_i$s are mutually vertex-disjoint as opposed to merely edge-disjoint
$endgroup$
– Mike
Mar 24 at 19:04
$begingroup$
...as the + notation in graph theory can be ambiguous!
$endgroup$
– Mike
Mar 24 at 19:17
$begingroup$
Thank you Mike for observation, I'm not very familiar with graph theory so I'm not aware of such misconseptions
$endgroup$
– VakiPitsi
Mar 25 at 14:33
$begingroup$
You may want to explain your notation further. What is $C_i$?
$endgroup$
– Mike
Mar 24 at 17:38
$begingroup$
You may want to explain your notation further. What is $C_i$?
$endgroup$
– Mike
Mar 24 at 17:38
$begingroup$
It's the standard notation for the cycle graph with i vertices
$endgroup$
– VakiPitsi
Mar 24 at 17:46
$begingroup$
It's the standard notation for the cycle graph with i vertices
$endgroup$
– VakiPitsi
Mar 24 at 17:46
1
1
$begingroup$
Thank you for the clarification, I see it now, I think I had misread the question. But [and I am not meaning to nitpick here] it would also be helpful to note in the statement of your problem that the $C_i$s are mutually vertex-disjoint as opposed to merely edge-disjoint
$endgroup$
– Mike
Mar 24 at 19:04
$begingroup$
Thank you for the clarification, I see it now, I think I had misread the question. But [and I am not meaning to nitpick here] it would also be helpful to note in the statement of your problem that the $C_i$s are mutually vertex-disjoint as opposed to merely edge-disjoint
$endgroup$
– Mike
Mar 24 at 19:04
$begingroup$
...as the + notation in graph theory can be ambiguous!
$endgroup$
– Mike
Mar 24 at 19:17
$begingroup$
...as the + notation in graph theory can be ambiguous!
$endgroup$
– Mike
Mar 24 at 19:17
$begingroup$
Thank you Mike for observation, I'm not very familiar with graph theory so I'm not aware of such misconseptions
$endgroup$
– VakiPitsi
Mar 25 at 14:33
$begingroup$
Thank you Mike for observation, I'm not very familiar with graph theory so I'm not aware of such misconseptions
$endgroup$
– VakiPitsi
Mar 25 at 14:33
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I am assuming you mean $G$ is the disjoint union of a set of cycles? Because of this I am just going to assume $G$ is connected to speed things up, the proof for $G$ being disconnected will follow immediately.
We note fairly quick that if $G=C_n$ then $L(G) cong C_n$ from the definition of a line graph.
Suppose $G cong L(G)$. By the definition of a line graph $$|V(L(G))|=|E(G)| qquad |E(L(G))|=|V(G)|,$$ however we now also have $$|V(L(G))|=|V(G)| qquad |E(L(G))|=|E(G)|,$$ thus $|V(G)|=|E(G)|$. As $G$ is connected this implies that $G$ is a cycle as required.
answered Mar 24 at 18:26
S. DewarS. Dewar
710210
$endgroup$
$begingroup$
Thank you! And also yes $G$ is connected and is also the disjoint union of the cycles $C_n$ sorry I didn't mention that I just started my courses on graph theory and I'm still not too familiar with the way the formal definitions should be written
$endgroup$
– VakiPitsi
Mar 25 at 13:10
1
$begingroup$
@VakiPitsi Glad I could help! I have found that graph theory has a lot of notation but much of it is non-standard. My advice would be that if you are in doubt whether it is clear, just state what your notation means, even if it possibly seems trivial.
$endgroup$
– S. Dewar
Mar 29 at 11:06
add a comment |
Your Answer
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%2f3160784%2fprove-that-a-graph-is-isomorphic-with-its-line-graph%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I am assuming you mean $G$ is the disjoint union of a set of cycles? Because of this I am just going to assume $G$ is connected to speed things up, the proof for $G$ being disconnected will follow immediately.
We note fairly quick that if $G=C_n$ then $L(G) cong C_n$ from the definition of a line graph.
Suppose $G cong L(G)$. By the definition of a line graph $$|V(L(G))|=|E(G)| qquad |E(L(G))|=|V(G)|,$$ however we now also have $$|V(L(G))|=|V(G)| qquad |E(L(G))|=|E(G)|,$$ thus $|V(G)|=|E(G)|$. As $G$ is connected this implies that $G$ is a cycle as required.
answered Mar 24 at 18:26
S. DewarS. Dewar
710210
$endgroup$
$begingroup$
Thank you! And also yes $G$ is connected and is also the disjoint union of the cycles $C_n$ sorry I didn't mention that I just started my courses on graph theory and I'm still not too familiar with the way the formal definitions should be written
$endgroup$
– VakiPitsi
Mar 25 at 13:10
1
$begingroup$
@VakiPitsi Glad I could help! I have found that graph theory has a lot of notation but much of it is non-standard. My advice would be that if you are in doubt whether it is clear, just state what your notation means, even if it possibly seems trivial.
$endgroup$
– S. Dewar
Mar 29 at 11:06
add a comment |
$begingroup$
I am assuming you mean $G$ is the disjoint union of a set of cycles? Because of this I am just going to assume $G$ is connected to speed things up, the proof for $G$ being disconnected will follow immediately.
We note fairly quick that if $G=C_n$ then $L(G) cong C_n$ from the definition of a line graph.
Suppose $G cong L(G)$. By the definition of a line graph $$|V(L(G))|=|E(G)| qquad |E(L(G))|=|V(G)|,$$ however we now also have $$|V(L(G))|=|V(G)| qquad |E(L(G))|=|E(G)|,$$ thus $|V(G)|=|E(G)|$. As $G$ is connected this implies that $G$ is a cycle as required.
answered Mar 24 at 18:26
S. DewarS. Dewar
710210
$endgroup$
$begingroup$
Thank you! And also yes $G$ is connected and is also the disjoint union of the cycles $C_n$ sorry I didn't mention that I just started my courses on graph theory and I'm still not too familiar with the way the formal definitions should be written
$endgroup$
– VakiPitsi
Mar 25 at 13:10
1
$begingroup$
@VakiPitsi Glad I could help! I have found that graph theory has a lot of notation but much of it is non-standard. My advice would be that if you are in doubt whether it is clear, just state what your notation means, even if it possibly seems trivial.
$endgroup$
– S. Dewar
Mar 29 at 11:06
add a comment |
$begingroup$
I am assuming you mean $G$ is the disjoint union of a set of cycles? Because of this I am just going to assume $G$ is connected to speed things up, the proof for $G$ being disconnected will follow immediately.
We note fairly quick that if $G=C_n$ then $L(G) cong C_n$ from the definition of a line graph.
Suppose $G cong L(G)$. By the definition of a line graph $$|V(L(G))|=|E(G)| qquad |E(L(G))|=|V(G)|,$$ however we now also have $$|V(L(G))|=|V(G)| qquad |E(L(G))|=|E(G)|,$$ thus $|V(G)|=|E(G)|$. As $G$ is connected this implies that $G$ is a cycle as required.
answered Mar 24 at 18:26
S. DewarS. Dewar
710210
$endgroup$
I am assuming you mean $G$ is the disjoint union of a set of cycles? Because of this I am just going to assume $G$ is connected to speed things up, the proof for $G$ being disconnected will follow immediately.
We note fairly quick that if $G=C_n$ then $L(G) cong C_n$ from the definition of a line graph.
Suppose $G cong L(G)$. By the definition of a line graph $$|V(L(G))|=|E(G)| qquad |E(L(G))|=|V(G)|,$$ however we now also have $$|V(L(G))|=|V(G)| qquad |E(L(G))|=|E(G)|,$$ thus $|V(G)|=|E(G)|$. As $G$ is connected this implies that $G$ is a cycle as required.
answered Mar 24 at 18:26
S. DewarS. Dewar
710210
answered Mar 24 at 18:26
S. DewarS. Dewar
710210
answered Mar 24 at 18:26
S. DewarS. Dewar
710210
answered Mar 24 at 18:26
S. DewarS. Dewar
710210
710210
$begingroup$
Thank you! And also yes $G$ is connected and is also the disjoint union of the cycles $C_n$ sorry I didn't mention that I just started my courses on graph theory and I'm still not too familiar with the way the formal definitions should be written
$endgroup$
– VakiPitsi
Mar 25 at 13:10
1
$begingroup$
@VakiPitsi Glad I could help! I have found that graph theory has a lot of notation but much of it is non-standard. My advice would be that if you are in doubt whether it is clear, just state what your notation means, even if it possibly seems trivial.
$endgroup$
– S. Dewar
Mar 29 at 11:06
add a comment |
$begingroup$
Thank you! And also yes $G$ is connected and is also the disjoint union of the cycles $C_n$ sorry I didn't mention that I just started my courses on graph theory and I'm still not too familiar with the way the formal definitions should be written
$endgroup$
– VakiPitsi
Mar 25 at 13:10
1
$begingroup$
@VakiPitsi Glad I could help! I have found that graph theory has a lot of notation but much of it is non-standard. My advice would be that if you are in doubt whether it is clear, just state what your notation means, even if it possibly seems trivial.
$endgroup$
– S. Dewar
Mar 29 at 11:06
$begingroup$
Thank you! And also yes $G$ is connected and is also the disjoint union of the cycles $C_n$ sorry I didn't mention that I just started my courses on graph theory and I'm still not too familiar with the way the formal definitions should be written
$endgroup$
– VakiPitsi
Mar 25 at 13:10
$begingroup$
Thank you! And also yes $G$ is connected and is also the disjoint union of the cycles $C_n$ sorry I didn't mention that I just started my courses on graph theory and I'm still not too familiar with the way the formal definitions should be written
$endgroup$
– VakiPitsi
Mar 25 at 13:10
1
1
$begingroup$
@VakiPitsi Glad I could help! I have found that graph theory has a lot of notation but much of it is non-standard. My advice would be that if you are in doubt whether it is clear, just state what your notation means, even if it possibly seems trivial.
$endgroup$
– S. Dewar
Mar 29 at 11:06
$begingroup$
@VakiPitsi Glad I could help! I have found that graph theory has a lot of notation but much of it is non-standard. My advice would be that if you are in doubt whether it is clear, just state what your notation means, even if it possibly seems trivial.
$endgroup$
– S. Dewar
Mar 29 at 11:06
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%2f3160784%2fprove-that-a-graph-is-isomorphic-with-its-line-graph%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$
You may want to explain your notation further. What is $C_i$?
$endgroup$
– Mike
Mar 24 at 17:38
$begingroup$
It's the standard notation for the cycle graph with i vertices
$endgroup$
– VakiPitsi
Mar 24 at 17:46
1
$begingroup$
Thank you for the clarification, I see it now, I think I had misread the question. But [and I am not meaning to nitpick here] it would also be helpful to note in the statement of your problem that the $C_i$s are mutually vertex-disjoint as opposed to merely edge-disjoint
$endgroup$
– Mike
Mar 24 at 19:04
$begingroup$
...as the + notation in graph theory can be ambiguous!
$endgroup$
– Mike
Mar 24 at 19:17
$begingroup$
Thank you Mike for observation, I'm not very familiar with graph theory so I'm not aware of such misconseptions
$endgroup$
– VakiPitsi
Mar 25 at 14:33