Number of edges in Graph where neighbors are 2-element subsets of 1,…n with a common element

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

1

Let $nge2$ be an integer. For the simple graph $G_n$, define the set of nodes as the set of subsets of size 2 from the set 1,2,...n, where nodes are neighbors iff they have a common element. For example, for $nge3$, the nodes 1,2 and 1,3 are neighbors of $G_n$. Find the number of edges for $G_100$

I figured to find the number of edges, I should just find the number of 2-element subsets that share a common element. I know the total number of subsets of size 2 should equal $n choose 2$, but I'm stuck on how to find the number of these subsets that share a common element.

Should I try finding the number of subsets with no common elements and subtract that from $ n choose 2$ or is there a more direct way? Any help/tips would be greatly appreciated.

combinatorics discrete-mathematics graph-theory

share|cite|improve this question

asked Jul 14 at 18:24

Adam G

363

add a comment | 

up vote
1
down vote

favorite

1

Let $nge2$ be an integer. For the simple graph $G_n$, define the set of nodes as the set of subsets of size 2 from the set 1,2,...n, where nodes are neighbors iff they have a common element. For example, for $nge3$, the nodes 1,2 and 1,3 are neighbors of $G_n$. Find the number of edges for $G_100$

I figured to find the number of edges, I should just find the number of 2-element subsets that share a common element. I know the total number of subsets of size 2 should equal $n choose 2$, but I'm stuck on how to find the number of these subsets that share a common element.

Should I try finding the number of subsets with no common elements and subtract that from $ n choose 2$ or is there a more direct way? Any help/tips would be greatly appreciated.

combinatorics discrete-mathematics graph-theory

share|cite|improve this question

asked Jul 14 at 18:24

Adam G

363

add a comment | 

up vote
1
down vote

favorite

1

up vote
1
down vote

favorite

1

1

Let $nge2$ be an integer. For the simple graph $G_n$, define the set of nodes as the set of subsets of size 2 from the set 1,2,...n, where nodes are neighbors iff they have a common element. For example, for $nge3$, the nodes 1,2 and 1,3 are neighbors of $G_n$. Find the number of edges for $G_100$

I figured to find the number of edges, I should just find the number of 2-element subsets that share a common element. I know the total number of subsets of size 2 should equal $n choose 2$, but I'm stuck on how to find the number of these subsets that share a common element.

Should I try finding the number of subsets with no common elements and subtract that from $ n choose 2$ or is there a more direct way? Any help/tips would be greatly appreciated.

combinatorics discrete-mathematics graph-theory

share|cite|improve this question

asked Jul 14 at 18:24

Adam G

363

Let $nge2$ be an integer. For the simple graph $G_n$, define the set of nodes as the set of subsets of size 2 from the set 1,2,...n, where nodes are neighbors iff they have a common element. For example, for $nge3$, the nodes 1,2 and 1,3 are neighbors of $G_n$. Find the number of edges for $G_100$

I figured to find the number of edges, I should just find the number of 2-element subsets that share a common element. I know the total number of subsets of size 2 should equal $n choose 2$, but I'm stuck on how to find the number of these subsets that share a common element.

Should I try finding the number of subsets with no common elements and subtract that from $ n choose 2$ or is there a more direct way? Any help/tips would be greatly appreciated.

combinatorics discrete-mathematics graph-theory

share|cite|improve this question

asked Jul 14 at 18:24

Adam G

363

share|cite|improve this question

share|cite|improve this question

asked Jul 14 at 18:24

Adam G

363

asked Jul 14 at 18:24

Adam G

363

asked Jul 14 at 18:24

Adam G

363

363

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
1
down vote

Your approach is the correct one. For a given vertex (i.e. $2$-element subset) try to figure out how many are its neighbor.

This is the same for each vertex, so it's enough to do this for the node $1,2$. You could do this directly, and just count the number that have a $1$ and the number that have a $2$: since it has to be a distinct subset (i.e. it can't have both a $1$ and a $2$), it must consist of:

• a one or two




• a number in $3,4,ldots,n$.

We have two choices for picking the $1$ or $2$, and $n - 2$ choices for the others. This means each node has degree $2cdot (n-2)$. To see how this relates to the number of edges, consider what happens when you add up all of the degrees.

share|cite|improve this answer

answered Jul 14 at 18:50

Marcus M

8,1731847

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2851836%2fnumber-of-edges-in-graph-where-neighbors-are-2-element-subsets-of-1-n-with%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote

Your approach is the correct one. For a given vertex (i.e. $2$-element subset) try to figure out how many are its neighbor.

This is the same for each vertex, so it's enough to do this for the node $1,2$. You could do this directly, and just count the number that have a $1$ and the number that have a $2$: since it has to be a distinct subset (i.e. it can't have both a $1$ and a $2$), it must consist of:

• a one or two




• a number in $3,4,ldots,n$.

We have two choices for picking the $1$ or $2$, and $n - 2$ choices for the others. This means each node has degree $2cdot (n-2)$. To see how this relates to the number of edges, consider what happens when you add up all of the degrees.

share|cite|improve this answer

answered Jul 14 at 18:50

Marcus M

8,1731847

add a comment | 

up vote
1
down vote

Your approach is the correct one. For a given vertex (i.e. $2$-element subset) try to figure out how many are its neighbor.

This is the same for each vertex, so it's enough to do this for the node $1,2$. You could do this directly, and just count the number that have a $1$ and the number that have a $2$: since it has to be a distinct subset (i.e. it can't have both a $1$ and a $2$), it must consist of:

• a one or two




• a number in $3,4,ldots,n$.

We have two choices for picking the $1$ or $2$, and $n - 2$ choices for the others. This means each node has degree $2cdot (n-2)$. To see how this relates to the number of edges, consider what happens when you add up all of the degrees.

share|cite|improve this answer

answered Jul 14 at 18:50

Marcus M

8,1731847

add a comment | 

up vote
1
down vote

up vote
1
down vote

Your approach is the correct one. For a given vertex (i.e. $2$-element subset) try to figure out how many are its neighbor.

This is the same for each vertex, so it's enough to do this for the node $1,2$. You could do this directly, and just count the number that have a $1$ and the number that have a $2$: since it has to be a distinct subset (i.e. it can't have both a $1$ and a $2$), it must consist of:

• a one or two




• a number in $3,4,ldots,n$.

We have two choices for picking the $1$ or $2$, and $n - 2$ choices for the others. This means each node has degree $2cdot (n-2)$. To see how this relates to the number of edges, consider what happens when you add up all of the degrees.

share|cite|improve this answer

answered Jul 14 at 18:50

Marcus M

8,1731847

Your approach is the correct one. For a given vertex (i.e. $2$-element subset) try to figure out how many are its neighbor.

This is the same for each vertex, so it's enough to do this for the node $1,2$. You could do this directly, and just count the number that have a $1$ and the number that have a $2$: since it has to be a distinct subset (i.e. it can't have both a $1$ and a $2$), it must consist of:

• a one or two




• a number in $3,4,ldots,n$.

We have two choices for picking the $1$ or $2$, and $n - 2$ choices for the others. This means each node has degree $2cdot (n-2)$. To see how this relates to the number of edges, consider what happens when you add up all of the degrees.

share|cite|improve this answer

answered Jul 14 at 18:50

Marcus M

8,1731847

share|cite|improve this answer

share|cite|improve this answer

answered Jul 14 at 18:50

Marcus M

8,1731847

answered Jul 14 at 18:50

Marcus M

8,1731847

answered Jul 14 at 18:50

Marcus M

8,1731847

8,1731847

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2851836%2fnumber-of-edges-in-graph-where-neighbors-are-2-element-subsets-of-1-n-with%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

Name Email

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

Name Email

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

Name Email

Name Email

Name

Email

Name Email

Name

Email