Self-complementary graph exercise
$begingroup$
I'm doing university exercises about planar graphs and they gave me the following:
Let G be a connected, self-complementary planar graph of order n and size
m having four vertices of degree two and the remaining vertices of degree d. If six faces of G are triangles and the remaining faces are pentagons, compute the values of d, n and m.
I'm not sure How Can I figure out the solicited values? I tried reach an equalization using the Euler form, the successions degree form and the sizes form for a complementary graph, but I had not success.
Has someone any idea ?
Thanks a lot!
graph-theory planar-graph
asked Dec 31 '18 at 0:02
BrunoBernBrunoBern
153
$endgroup$
add a comment |
$begingroup$
I'm doing university exercises about planar graphs and they gave me the following:
Let G be a connected, self-complementary planar graph of order n and size
m having four vertices of degree two and the remaining vertices of degree d. If six faces of G are triangles and the remaining faces are pentagons, compute the values of d, n and m.
I'm not sure How Can I figure out the solicited values? I tried reach an equalization using the Euler form, the successions degree form and the sizes form for a complementary graph, but I had not success.
Has someone any idea ?
Thanks a lot!
graph-theory planar-graph
asked Dec 31 '18 at 0:02
BrunoBernBrunoBern
153
$endgroup$
add a comment |
$begingroup$
I'm doing university exercises about planar graphs and they gave me the following:
Let G be a connected, self-complementary planar graph of order n and size
m having four vertices of degree two and the remaining vertices of degree d. If six faces of G are triangles and the remaining faces are pentagons, compute the values of d, n and m.
I'm not sure How Can I figure out the solicited values? I tried reach an equalization using the Euler form, the successions degree form and the sizes form for a complementary graph, but I had not success.
Has someone any idea ?
Thanks a lot!
graph-theory planar-graph
asked Dec 31 '18 at 0:02
BrunoBernBrunoBern
153
$endgroup$
I'm doing university exercises about planar graphs and they gave me the following:
Let G be a connected, self-complementary planar graph of order n and size
m having four vertices of degree two and the remaining vertices of degree d. If six faces of G are triangles and the remaining faces are pentagons, compute the values of d, n and m.
I'm not sure How Can I figure out the solicited values? I tried reach an equalization using the Euler form, the successions degree form and the sizes form for a complementary graph, but I had not success.
Has someone any idea ?
Thanks a lot!
graph-theory planar-graph
graph-theory planar-graph
asked Dec 31 '18 at 0:02
BrunoBernBrunoBern
153
asked Dec 31 '18 at 0:02
BrunoBernBrunoBern
153
asked Dec 31 '18 at 0:02
BrunoBernBrunoBern
153
asked Dec 31 '18 at 0:02
BrunoBernBrunoBern
153
asked Dec 31 '18 at 0:02
BrunoBernBrunoBern
153
153
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Since G is self-complementary, it has half the number of edges as a complete graph of the same order.
$$m = frac{n(n-1)}{4} = 4+(n-4)frac{d}{2}$$
$$ n^2-n = 16+2nd-8d $$
Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)
Check for $d=5$:
$$ n^2-n = 16+10n-40 $$
$$ n^2-11n+24=0 implies n={3,8}$$
In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.
I will leave it to you to find the graph. Hint: add to the tetrahedron.
answered Dec 31 '18 at 0:44
Zachary HunterZachary Hunter
55611
$endgroup$
$begingroup$
Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
$endgroup$
– BrunoBern
Dec 31 '18 at 3:33
$begingroup$
@BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:37
$begingroup$
A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:40
$begingroup$
Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
$endgroup$
– BrunoBern
Dec 31 '18 at 15:06
$begingroup$
Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 15:19
|
show 1 more 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%2f3057301%2fself-complementary-graph-exercise%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$
Since G is self-complementary, it has half the number of edges as a complete graph of the same order.
$$m = frac{n(n-1)}{4} = 4+(n-4)frac{d}{2}$$
$$ n^2-n = 16+2nd-8d $$
Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)
Check for $d=5$:
$$ n^2-n = 16+10n-40 $$
$$ n^2-11n+24=0 implies n={3,8}$$
In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.
I will leave it to you to find the graph. Hint: add to the tetrahedron.
answered Dec 31 '18 at 0:44
Zachary HunterZachary Hunter
55611
$endgroup$
$begingroup$
Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
$endgroup$
– BrunoBern
Dec 31 '18 at 3:33
$begingroup$
@BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:37
$begingroup$
A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:40
$begingroup$
Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
$endgroup$
– BrunoBern
Dec 31 '18 at 15:06
$begingroup$
Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 15:19
|
show 1 more comment
$begingroup$
Since G is self-complementary, it has half the number of edges as a complete graph of the same order.
$$m = frac{n(n-1)}{4} = 4+(n-4)frac{d}{2}$$
$$ n^2-n = 16+2nd-8d $$
Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)
Check for $d=5$:
$$ n^2-n = 16+10n-40 $$
$$ n^2-11n+24=0 implies n={3,8}$$
In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.
I will leave it to you to find the graph. Hint: add to the tetrahedron.
answered Dec 31 '18 at 0:44
Zachary HunterZachary Hunter
55611
$endgroup$
$begingroup$
Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
$endgroup$
– BrunoBern
Dec 31 '18 at 3:33
$begingroup$
@BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:37
$begingroup$
A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:40
$begingroup$
Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
$endgroup$
– BrunoBern
Dec 31 '18 at 15:06
$begingroup$
Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 15:19
|
show 1 more comment
$begingroup$
Since G is self-complementary, it has half the number of edges as a complete graph of the same order.
$$m = frac{n(n-1)}{4} = 4+(n-4)frac{d}{2}$$
$$ n^2-n = 16+2nd-8d $$
Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)
Check for $d=5$:
$$ n^2-n = 16+10n-40 $$
$$ n^2-11n+24=0 implies n={3,8}$$
In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.
I will leave it to you to find the graph. Hint: add to the tetrahedron.
answered Dec 31 '18 at 0:44
Zachary HunterZachary Hunter
55611
$endgroup$
Since G is self-complementary, it has half the number of edges as a complete graph of the same order.
$$m = frac{n(n-1)}{4} = 4+(n-4)frac{d}{2}$$
$$ n^2-n = 16+2nd-8d $$
Since G is planar, we know that $d<6$. (we can contract the vertices of degree two, and then Euler's formula is violated)
Check for $d=5$:
$$ n^2-n = 16+10n-40 $$
$$ n^2-11n+24=0 implies n={3,8}$$
In hindsight, we know that $n = 8$ because the number of vertices with degree 2 and $d$ must be equal. And then, you must realize that $n-1-d=2$, so that the vertices of degree $d$ have degree 2 in the complement.
I will leave it to you to find the graph. Hint: add to the tetrahedron.
answered Dec 31 '18 at 0:44
Zachary HunterZachary Hunter
55611
edited Dec 31 '18 at 2:07
answered Dec 31 '18 at 0:44
Zachary HunterZachary Hunter
55611
answered Dec 31 '18 at 0:44
Zachary HunterZachary Hunter
55611
answered Dec 31 '18 at 0:44
Zachary HunterZachary Hunter
55611
55611
$begingroup$
Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
$endgroup$
– BrunoBern
Dec 31 '18 at 3:33
$begingroup$
@BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:37
$begingroup$
A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:40
$begingroup$
Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
$endgroup$
– BrunoBern
Dec 31 '18 at 15:06
$begingroup$
Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 15:19
|
show 1 more comment
$begingroup$
Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
$endgroup$
– BrunoBern
Dec 31 '18 at 3:33
$begingroup$
@BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:37
$begingroup$
A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:40
$begingroup$
Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
$endgroup$
– BrunoBern
Dec 31 '18 at 15:06
$begingroup$
Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 15:19
$begingroup$
Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
$endgroup$
– BrunoBern
Dec 31 '18 at 3:33
$begingroup$
Hi!, Thanks you for the answer. I don't understand why the number of vertices with degree 2 and d must be equals. Sorry, but I'm beginner with this topics.
$endgroup$
– BrunoBern
Dec 31 '18 at 3:33
$begingroup$
@BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:37
$begingroup$
@BrunoBern all vertices will either have degrees 2 or $d$. When you take the complement, the degree of every vertex will change. For it to be self complementary, in the complement of G, you should have the same number of vertices if each degree as before.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:37
$begingroup$
A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:40
$begingroup$
A more accurate statement would be, you have four vertices of degree two, and need to have exactly four vertices which will have degree two in the complement.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 3:40
$begingroup$
Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
$endgroup$
– BrunoBern
Dec 31 '18 at 15:06
$begingroup$
Hi @ZacharyHunter, thanks again for the answer. My last question is: How did you infer that D is less than 6 ? Because I read different posts and I looked at internet, but I just found one property, whose explains: "One vertex in the planar graph has at least five degrees", but this property could be reached with the existence of four vertices with degree 2.
$endgroup$
– BrunoBern
Dec 31 '18 at 15:06
$begingroup$
Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 15:19
$begingroup$
Manipulating Euler's formula, you can get the conclusion that $E leq 3V-6$ by assuming each face has degree three. Applying HST, we know the sum of degrees is $2E leq 6V-12$. However, this is only true assuming the graph is simple, and does not have faces of degree two. Since we were contracting vertices, this is an unsound assumption, in hindsight. It was a bit of a practical caveman technique, where you check a few values until something is right. Since I knew that $d$ is fairly limited, I didn't sweat the details. However, my last paragraph gets everything with much nicer logic.
$endgroup$
– Zachary Hunter
Dec 31 '18 at 15:19
|
show 1 more 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%2f3057301%2fself-complementary-graph-exercise%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
