Mixing
Friendship theorem: need help with part of proof.
$begingroup$
Suppose $G$ is a simple graph such that every two of its vertices have exactly one common neighbor. The friendship theorem says that $G$ must be a friendship graph (a bunch of triangles joined at a single vertex): 
The hint in the problem says to suppose for a contradiction that $G$ is not such a graph. Then supposedly $G$ must be regular (all vertices have same degree), but I don't see why. Can someone help? Once I have this, I see how to get the contradiction to finish the proof.
EDIT: I posted a my solution below. If you are interested, please let me know if it looks ok. If you have a simpler proof feel free to post it, I'd like to see it.
graph-theory
asked Jun 30 '15 at 10:26
Forever MozartForever Mozart
5,55821640
$endgroup$
add a comment |
$begingroup$
Suppose $G$ is a simple graph such that every two of its vertices have exactly one common neighbor. The friendship theorem says that $G$ must be a friendship graph (a bunch of triangles joined at a single vertex):
The hint in the problem says to suppose for a contradiction that $G$ is not such a graph. Then supposedly $G$ must be regular (all vertices have same degree), but I don't see why. Can someone help? Once I have this, I see how to get the contradiction to finish the proof.
EDIT: I posted a my solution below. If you are interested, please let me know if it looks ok. If you have a simpler proof feel free to post it, I'd like to see it.
graph-theory
asked Jun 30 '15 at 10:26
Forever MozartForever Mozart
5,55821640
$endgroup$
$begingroup$
Using induction, deduce that $N[v]$ is a friendship graph; further for two vertices v and w, define $f:N(v) to N(w)$ as: f(x)=unique common neighbor of x and w. Try to show that f is injective and hence $deg(v) leq deg(w)$.
$endgroup$
– Aravind
Jun 30 '15 at 11:28
$begingroup$
@Aravind Thanks for your comment. I now have a proof, though it is a bit complicated. I will post it here sometime today.
$endgroup$
– Forever Mozart
Jun 30 '15 at 14:05
add a comment |
$begingroup$
Suppose $G$ is a simple graph such that every two of its vertices have exactly one common neighbor. The friendship theorem says that $G$ must be a friendship graph (a bunch of triangles joined at a single vertex):
The hint in the problem says to suppose for a contradiction that $G$ is not such a graph. Then supposedly $G$ must be regular (all vertices have same degree), but I don't see why. Can someone help? Once I have this, I see how to get the contradiction to finish the proof.
EDIT: I posted a my solution below. If you are interested, please let me know if it looks ok. If you have a simpler proof feel free to post it, I'd like to see it.
graph-theory
asked Jun 30 '15 at 10:26
Forever MozartForever Mozart
5,55821640
$endgroup$
Suppose $G$ is a simple graph such that every two of its vertices have exactly one common neighbor. The friendship theorem says that $G$ must be a friendship graph (a bunch of triangles joined at a single vertex):
The hint in the problem says to suppose for a contradiction that $G$ is not such a graph. Then supposedly $G$ must be regular (all vertices have same degree), but I don't see why. Can someone help? Once I have this, I see how to get the contradiction to finish the proof.
EDIT: I posted a my solution below. If you are interested, please let me know if it looks ok. If you have a simpler proof feel free to post it, I'd like to see it.
graph-theory
graph-theory
asked Jun 30 '15 at 10:26
Forever MozartForever Mozart
5,55821640
asked Jun 30 '15 at 10:26
Forever MozartForever Mozart
5,55821640
edited Jun 30 '15 at 14:37
Forever Mozart
asked Jun 30 '15 at 10:26
Forever MozartForever Mozart
5,55821640
asked Jun 30 '15 at 10:26
Forever MozartForever Mozart
5,55821640
asked Jun 30 '15 at 10:26
Forever MozartForever Mozart
5,55821640
5,55821640
$begingroup$
Using induction, deduce that $N[v]$ is a friendship graph; further for two vertices v and w, define $f:N(v) to N(w)$ as: f(x)=unique common neighbor of x and w. Try to show that f is injective and hence $deg(v) leq deg(w)$.
$endgroup$
– Aravind
Jun 30 '15 at 11:28
$begingroup$
@Aravind Thanks for your comment. I now have a proof, though it is a bit complicated. I will post it here sometime today.
$endgroup$
– Forever Mozart
Jun 30 '15 at 14:05
add a comment |
$begingroup$
Using induction, deduce that $N[v]$ is a friendship graph; further for two vertices v and w, define $f:N(v) to N(w)$ as: f(x)=unique common neighbor of x and w. Try to show that f is injective and hence $deg(v) leq deg(w)$.
$endgroup$
– Aravind
Jun 30 '15 at 11:28
$begingroup$
@Aravind Thanks for your comment. I now have a proof, though it is a bit complicated. I will post it here sometime today.
$endgroup$
– Forever Mozart
Jun 30 '15 at 14:05
$begingroup$
Using induction, deduce that $N[v]$ is a friendship graph; further for two vertices v and w, define $f:N(v) to N(w)$ as: f(x)=unique common neighbor of x and w. Try to show that f is injective and hence $deg(v) leq deg(w)$.
$endgroup$
– Aravind
Jun 30 '15 at 11:28
$begingroup$
Using induction, deduce that $N[v]$ is a friendship graph; further for two vertices v and w, define $f:N(v) to N(w)$ as: f(x)=unique common neighbor of x and w. Try to show that f is injective and hence $deg(v) leq deg(w)$.
$endgroup$
– Aravind
Jun 30 '15 at 11:28
$begingroup$
@Aravind Thanks for your comment. I now have a proof, though it is a bit complicated. I will post it here sometime today.
$endgroup$
– Forever Mozart
Jun 30 '15 at 14:05
$begingroup$
@Aravind Thanks for your comment. I now have a proof, though it is a bit complicated. I will post it here sometime today.
$endgroup$
– Forever Mozart
Jun 30 '15 at 14:05
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Suppose every two vertices in $G$ have exactly one common neighbor, but $G$ is not a friendship graph. We show $G$ is regular.
Let $u$ and $v$ be vertices of $G$. We define an injection $f:N(u)to N(v)$, yielding $|N(u)|leq |N(v)|$. By symmetry the reverse inequality will follow.
Case 1: $vnotin N(u)$. Let $f(x)$ be the neighbor between $x$ and $v$. If $xneq y$ then by uniqueness of common neighbors $f(x)=f(y)$ would imply $u=f(x)$, but then $vin N(u)$.
Case 2: $vin N(u)$. Since $G$ is not a friendship graph, i.e. it has no vertex that is connected to all other vertices, there is a vertex $wnotin N(u)$. For each $xin N(u)$ let $x'$ be the vertex between $x$ and $w$. Define $f(v)=v'$ and for all other $x$ let $f(x)$ be the vertex between $x'$ and $v$.
If $xneq vin N(u)$ but $f(x)=f(v)$, then by uniquess of the common neighbor of $x$ and $v$ we have $u=f(v)in N(w)$, a contradiction.
If $xneq yin N(u)$ with $xneq vneq y$ but $f(x)=f(y)$, then by uniqueness of the common neighbor of $x'$ and $y'$ we have $w=vin N(u)$, a contradiction.
answered Jun 30 '15 at 14:32
Forever MozartForever Mozart
5,55821640
$endgroup$
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%2f1344385%2ffriendship-theorem-need-help-with-part-of-proof%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$
Suppose every two vertices in $G$ have exactly one common neighbor, but $G$ is not a friendship graph. We show $G$ is regular.
Let $u$ and $v$ be vertices of $G$. We define an injection $f:N(u)to N(v)$, yielding $|N(u)|leq |N(v)|$. By symmetry the reverse inequality will follow.
Case 1: $vnotin N(u)$. Let $f(x)$ be the neighbor between $x$ and $v$. If $xneq y$ then by uniqueness of common neighbors $f(x)=f(y)$ would imply $u=f(x)$, but then $vin N(u)$.
Case 2: $vin N(u)$. Since $G$ is not a friendship graph, i.e. it has no vertex that is connected to all other vertices, there is a vertex $wnotin N(u)$. For each $xin N(u)$ let $x'$ be the vertex between $x$ and $w$. Define $f(v)=v'$ and for all other $x$ let $f(x)$ be the vertex between $x'$ and $v$.
If $xneq vin N(u)$ but $f(x)=f(v)$, then by uniquess of the common neighbor of $x$ and $v$ we have $u=f(v)in N(w)$, a contradiction.
If $xneq yin N(u)$ with $xneq vneq y$ but $f(x)=f(y)$, then by uniqueness of the common neighbor of $x'$ and $y'$ we have $w=vin N(u)$, a contradiction.
answered Jun 30 '15 at 14:32
Forever MozartForever Mozart
5,55821640
$endgroup$
add a comment |
$begingroup$
Suppose every two vertices in $G$ have exactly one common neighbor, but $G$ is not a friendship graph. We show $G$ is regular.
Let $u$ and $v$ be vertices of $G$. We define an injection $f:N(u)to N(v)$, yielding $|N(u)|leq |N(v)|$. By symmetry the reverse inequality will follow.
Case 1: $vnotin N(u)$. Let $f(x)$ be the neighbor between $x$ and $v$. If $xneq y$ then by uniqueness of common neighbors $f(x)=f(y)$ would imply $u=f(x)$, but then $vin N(u)$.
Case 2: $vin N(u)$. Since $G$ is not a friendship graph, i.e. it has no vertex that is connected to all other vertices, there is a vertex $wnotin N(u)$. For each $xin N(u)$ let $x'$ be the vertex between $x$ and $w$. Define $f(v)=v'$ and for all other $x$ let $f(x)$ be the vertex between $x'$ and $v$.
If $xneq vin N(u)$ but $f(x)=f(v)$, then by uniquess of the common neighbor of $x$ and $v$ we have $u=f(v)in N(w)$, a contradiction.
If $xneq yin N(u)$ with $xneq vneq y$ but $f(x)=f(y)$, then by uniqueness of the common neighbor of $x'$ and $y'$ we have $w=vin N(u)$, a contradiction.
answered Jun 30 '15 at 14:32
Forever MozartForever Mozart
5,55821640
$endgroup$
add a comment |
$begingroup$
Suppose every two vertices in $G$ have exactly one common neighbor, but $G$ is not a friendship graph. We show $G$ is regular.
Let $u$ and $v$ be vertices of $G$. We define an injection $f:N(u)to N(v)$, yielding $|N(u)|leq |N(v)|$. By symmetry the reverse inequality will follow.
Case 1: $vnotin N(u)$. Let $f(x)$ be the neighbor between $x$ and $v$. If $xneq y$ then by uniqueness of common neighbors $f(x)=f(y)$ would imply $u=f(x)$, but then $vin N(u)$.
Case 2: $vin N(u)$. Since $G$ is not a friendship graph, i.e. it has no vertex that is connected to all other vertices, there is a vertex $wnotin N(u)$. For each $xin N(u)$ let $x'$ be the vertex between $x$ and $w$. Define $f(v)=v'$ and for all other $x$ let $f(x)$ be the vertex between $x'$ and $v$.
If $xneq vin N(u)$ but $f(x)=f(v)$, then by uniquess of the common neighbor of $x$ and $v$ we have $u=f(v)in N(w)$, a contradiction.
If $xneq yin N(u)$ with $xneq vneq y$ but $f(x)=f(y)$, then by uniqueness of the common neighbor of $x'$ and $y'$ we have $w=vin N(u)$, a contradiction.
answered Jun 30 '15 at 14:32
Forever MozartForever Mozart
5,55821640
$endgroup$
Suppose every two vertices in $G$ have exactly one common neighbor, but $G$ is not a friendship graph. We show $G$ is regular.
Let $u$ and $v$ be vertices of $G$. We define an injection $f:N(u)to N(v)$, yielding $|N(u)|leq |N(v)|$. By symmetry the reverse inequality will follow.
Case 1: $vnotin N(u)$. Let $f(x)$ be the neighbor between $x$ and $v$. If $xneq y$ then by uniqueness of common neighbors $f(x)=f(y)$ would imply $u=f(x)$, but then $vin N(u)$.
Case 2: $vin N(u)$. Since $G$ is not a friendship graph, i.e. it has no vertex that is connected to all other vertices, there is a vertex $wnotin N(u)$. For each $xin N(u)$ let $x'$ be the vertex between $x$ and $w$. Define $f(v)=v'$ and for all other $x$ let $f(x)$ be the vertex between $x'$ and $v$.
If $xneq vin N(u)$ but $f(x)=f(v)$, then by uniquess of the common neighbor of $x$ and $v$ we have $u=f(v)in N(w)$, a contradiction.
If $xneq yin N(u)$ with $xneq vneq y$ but $f(x)=f(y)$, then by uniqueness of the common neighbor of $x'$ and $y'$ we have $w=vin N(u)$, a contradiction.
answered Jun 30 '15 at 14:32
Forever MozartForever Mozart
5,55821640
edited Jun 30 '15 at 14:38
answered Jun 30 '15 at 14:32
Forever MozartForever Mozart
5,55821640
answered Jun 30 '15 at 14:32
Forever MozartForever Mozart
5,55821640
answered Jun 30 '15 at 14:32
Forever MozartForever Mozart
5,55821640
5,55821640
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%2f1344385%2ffriendship-theorem-need-help-with-part-of-proof%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$
Using induction, deduce that $N[v]$ is a friendship graph; further for two vertices v and w, define $f:N(v) to N(w)$ as: f(x)=unique common neighbor of x and w. Try to show that f is injective and hence $deg(v) leq deg(w)$.
$endgroup$
– Aravind
Jun 30 '15 at 11:28
$begingroup$
@Aravind Thanks for your comment. I now have a proof, though it is a bit complicated. I will post it here sometime today.
$endgroup$
– Forever Mozart
Jun 30 '15 at 14:05