Calculating number of edges in a graph
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
The prompt is to find the number of edges of graph with $36$ vertices given that from every $4$ vertices, at least $2$ of them have to have an edge between them. We must prove that the graph G has at least 105 edges or find some non-trivial lower limit on the number of edges.
If we join $2$ vertices of all the $36$ vertices, we are left with $18$ edges, how is this possible, how should I go on about solving a problem like this?
I know that $2|E| = deg(v)$ by handshake theorem, how should I find the degree of each vertex here?
discrete-mathematics graph-theory
asked Aug 26 at 21:32
Archetype2142
462313
add a comment |Â
up vote
1
down vote
favorite
The prompt is to find the number of edges of graph with $36$ vertices given that from every $4$ vertices, at least $2$ of them have to have an edge between them. We must prove that the graph G has at least 105 edges or find some non-trivial lower limit on the number of edges.
If we join $2$ vertices of all the $36$ vertices, we are left with $18$ edges, how is this possible, how should I go on about solving a problem like this?
I know that $2|E| = deg(v)$ by handshake theorem, how should I find the degree of each vertex here?
discrete-mathematics graph-theory
asked Aug 26 at 21:32
Archetype2142
462313
If you divide up the 36 vertices into pairs $1,2, 3,4, 5,6, dots$ and connect every pair by an edge, that doesn't accomplish the task in the prompt: the four vertices $1,3,5,7$ have no edges between them.
– Misha Lavrov
Aug 26 at 21:40
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
The prompt is to find the number of edges of graph with $36$ vertices given that from every $4$ vertices, at least $2$ of them have to have an edge between them. We must prove that the graph G has at least 105 edges or find some non-trivial lower limit on the number of edges.
If we join $2$ vertices of all the $36$ vertices, we are left with $18$ edges, how is this possible, how should I go on about solving a problem like this?
I know that $2|E| = deg(v)$ by handshake theorem, how should I find the degree of each vertex here?
discrete-mathematics graph-theory
asked Aug 26 at 21:32
Archetype2142
462313
The prompt is to find the number of edges of graph with $36$ vertices given that from every $4$ vertices, at least $2$ of them have to have an edge between them. We must prove that the graph G has at least 105 edges or find some non-trivial lower limit on the number of edges.
If we join $2$ vertices of all the $36$ vertices, we are left with $18$ edges, how is this possible, how should I go on about solving a problem like this?
I know that $2|E| = deg(v)$ by handshake theorem, how should I find the degree of each vertex here?
discrete-mathematics graph-theory
asked Aug 26 at 21:32
Archetype2142
462313
edited Aug 26 at 22:48
user550230
asked Aug 26 at 21:32
Archetype2142
462313
asked Aug 26 at 21:32
Archetype2142
462313
asked Aug 26 at 21:32
Archetype2142
462313
462313
If you divide up the 36 vertices into pairs $1,2, 3,4, 5,6, dots$ and connect every pair by an edge, that doesn't accomplish the task in the prompt: the four vertices $1,3,5,7$ have no edges between them.
– Misha Lavrov
Aug 26 at 21:40
add a comment |Â
If you divide up the 36 vertices into pairs $1,2, 3,4, 5,6, dots$ and connect every pair by an edge, that doesn't accomplish the task in the prompt: the four vertices $1,3,5,7$ have no edges between them.
– Misha Lavrov
Aug 26 at 21:40
If you divide up the 36 vertices into pairs $1,2, 3,4, 5,6, dots$ and connect every pair by an edge, that doesn't accomplish the task in the prompt: the four vertices $1,3,5,7$ have no edges between them.
– Misha Lavrov
Aug 26 at 21:40
If you divide up the 36 vertices into pairs $1,2, 3,4, 5,6, dots$ and connect every pair by an edge, that doesn't accomplish the task in the prompt: the four vertices $1,3,5,7$ have no edges between them.
– Misha Lavrov
Aug 26 at 21:40
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Consider the set of all subgraphs of $G$ that have four vertices. There are $36choose 4$ such graphs. For each such subgraph $H$, count the number of edges $e(H)$ in it. Then calculate $sum_H e(H)$ in two ways. One way is to note that every edge appears $34 choose 2$ many times. So $sum_H e(H)=e(G) times 34 choose 2$. On the other hand, each subgraph $H$ has at least one edge, so $sum_H e(H) geq 36 choose 4$. In other words,
$$e(G) times 34 choose 2 geq 36 choose 4.$$
Simplifying both sides gives $e(G) geq 105$.
answered Aug 26 at 22:16
Marco
1,55917
Why does every edge appear $binom342$ times and not $binom362$?
– Archetype2142
Aug 27 at 7:08
1
Because that edge already has two vertices and to make a subgraph with four vertices we need two other vertices out of the remaining 34.
– Marco
Aug 27 at 10:54
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Consider the set of all subgraphs of $G$ that have four vertices. There are $36choose 4$ such graphs. For each such subgraph $H$, count the number of edges $e(H)$ in it. Then calculate $sum_H e(H)$ in two ways. One way is to note that every edge appears $34 choose 2$ many times. So $sum_H e(H)=e(G) times 34 choose 2$. On the other hand, each subgraph $H$ has at least one edge, so $sum_H e(H) geq 36 choose 4$. In other words,
$$e(G) times 34 choose 2 geq 36 choose 4.$$
Simplifying both sides gives $e(G) geq 105$.
answered Aug 26 at 22:16
Marco
1,55917
Why does every edge appear $binom342$ times and not $binom362$?
– Archetype2142
Aug 27 at 7:08
1
Because that edge already has two vertices and to make a subgraph with four vertices we need two other vertices out of the remaining 34.
– Marco
Aug 27 at 10:54
add a comment |Â
up vote
1
down vote
accepted
Consider the set of all subgraphs of $G$ that have four vertices. There are $36choose 4$ such graphs. For each such subgraph $H$, count the number of edges $e(H)$ in it. Then calculate $sum_H e(H)$ in two ways. One way is to note that every edge appears $34 choose 2$ many times. So $sum_H e(H)=e(G) times 34 choose 2$. On the other hand, each subgraph $H$ has at least one edge, so $sum_H e(H) geq 36 choose 4$. In other words,
$$e(G) times 34 choose 2 geq 36 choose 4.$$
Simplifying both sides gives $e(G) geq 105$.
answered Aug 26 at 22:16
Marco
1,55917
Why does every edge appear $binom342$ times and not $binom362$?
– Archetype2142
Aug 27 at 7:08
1
Because that edge already has two vertices and to make a subgraph with four vertices we need two other vertices out of the remaining 34.
– Marco
Aug 27 at 10:54
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Consider the set of all subgraphs of $G$ that have four vertices. There are $36choose 4$ such graphs. For each such subgraph $H$, count the number of edges $e(H)$ in it. Then calculate $sum_H e(H)$ in two ways. One way is to note that every edge appears $34 choose 2$ many times. So $sum_H e(H)=e(G) times 34 choose 2$. On the other hand, each subgraph $H$ has at least one edge, so $sum_H e(H) geq 36 choose 4$. In other words,
$$e(G) times 34 choose 2 geq 36 choose 4.$$
Simplifying both sides gives $e(G) geq 105$.
answered Aug 26 at 22:16
Marco
1,55917
Consider the set of all subgraphs of $G$ that have four vertices. There are $36choose 4$ such graphs. For each such subgraph $H$, count the number of edges $e(H)$ in it. Then calculate $sum_H e(H)$ in two ways. One way is to note that every edge appears $34 choose 2$ many times. So $sum_H e(H)=e(G) times 34 choose 2$. On the other hand, each subgraph $H$ has at least one edge, so $sum_H e(H) geq 36 choose 4$. In other words,
$$e(G) times 34 choose 2 geq 36 choose 4.$$
Simplifying both sides gives $e(G) geq 105$.
answered Aug 26 at 22:16
Marco
1,55917
answered Aug 26 at 22:16
Marco
1,55917
answered Aug 26 at 22:16
Marco
1,55917
answered Aug 26 at 22:16
Marco
1,55917
1,55917
Why does every edge appear $binom342$ times and not $binom362$?
– Archetype2142
Aug 27 at 7:08
1
Because that edge already has two vertices and to make a subgraph with four vertices we need two other vertices out of the remaining 34.
– Marco
Aug 27 at 10:54
add a comment |Â
Why does every edge appear $binom342$ times and not $binom362$?
– Archetype2142
Aug 27 at 7:08
1
Because that edge already has two vertices and to make a subgraph with four vertices we need two other vertices out of the remaining 34.
– Marco
Aug 27 at 10:54
Why does every edge appear $binom342$ times and not $binom362$?
– Archetype2142
Aug 27 at 7:08
Why does every edge appear $binom342$ times and not $binom362$?
– Archetype2142
Aug 27 at 7:08
1
1
Because that edge already has two vertices and to make a subgraph with four vertices we need two other vertices out of the remaining 34.
– Marco
Aug 27 at 10:54
Because that edge already has two vertices and to make a subgraph with four vertices we need two other vertices out of the remaining 34.
– Marco
Aug 27 at 10:54
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2895545%2fcalculating-number-of-edges-in-a-graph%23new-answer', 'question_page');
);
Post as a guest
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
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
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
If you divide up the 36 vertices into pairs $1,2, 3,4, 5,6, dots$ and connect every pair by an edge, that doesn't accomplish the task in the prompt: the four vertices $1,3,5,7$ have no edges between them.
– Misha Lavrov
Aug 26 at 21:40