Fdtxjr

Fundamental Solution of the Pell Equation

How to tell that you are a giant?

Why did the Falcon Heavy center core fall off the ASDS OCISLY barge?

Generate an RGB colour grid

illegal generic type for instanceof when using local classes

2001: A Space Odyssey's use of the song "Daisy Bell" (Bicycle Built for Two); life imitates art or vice-versa?

Are two submodules (where one is contained in the other) isomorphic if their quotientmodules are isomorphic?

What is a non-alternating simple group with big order, but relatively few conjugacy classes?

How would the world control an invulnerable immortal mass murderer?

Is there a program I can run on the C64 to speed up booting of a game?

Can a USB port passively 'listen only'?

Bete Noir -- no dairy

How to bypass password on Windows XP account?

What exactly is a "Meth" in Altered Carbon?

Selecting the same column from Different rows Based on Different Criteria

Is there a (better) way to access $wpdb results?

Why are there no cargo aircraft with "flying wing" design?

What does this icon in iOS Stardew Valley mean?

Is it ethical to give a final exam after the professor has quit before teaching the remaining chapters of the course?

What's the purpose of writing one's academic biography in the third person?

Denied boarding although I have proper visa and documentation. To whom should I make a complaint?

How to deal with a team lead who never gives me credit?

porting install scripts : can rpm replace apt?

Echoing a tail command produces unexpected output?

Number of edges in a transformation graph

2

$begingroup$

Having a problem that came up with using an old exercise book(so i have no solution to check or if is valid).

for a simple non-directed graph $G$ of order $n$ and size $m>1,L(G)$ (another graph) is defined as:

a)Every vertex of $L(G)$ is an edge of $G (1-1$ function)

b)$2$ vertices of $L(G)$ are connected by an edge iff the equivalent edges in $G$ have a common vertex

Prove that the number of edges of $L(G)$ $$sum_uin V(G)binomd(u)2$$(binomial coeficient).

My workprocess so far:By having a $1-1$ ratio of vertices $(L(G)$ - edges($G$) i can show that $n$ of $L(G)$ is equal to $sum d(u)/2$. I need the concept especialy of b) explained to me.

combinatorics discrete-mathematics graph-theory

share|cite|improve this question

edited Mar 26 at 16:26

Shubham Johri

5,668918

asked Mar 26 at 16:03

ChonChonChonChon

183

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I believe you meant there is a bijection between $V(L(G))$ and the set of edges of $G$.
  $endgroup$
  – Shubham Johri
  Mar 26 at 16:42
  

  
  
  
  

add a comment | 

2

$begingroup$

Having a problem that came up with using an old exercise book(so i have no solution to check or if is valid).

for a simple non-directed graph $G$ of order $n$ and size $m>1,L(G)$ (another graph) is defined as:

a)Every vertex of $L(G)$ is an edge of $G (1-1$ function)

b)$2$ vertices of $L(G)$ are connected by an edge iff the equivalent edges in $G$ have a common vertex

Prove that the number of edges of $L(G)$ $$sum_uin V(G)binomd(u)2$$(binomial coeficient).

My workprocess so far:By having a $1-1$ ratio of vertices $(L(G)$ - edges($G$) i can show that $n$ of $L(G)$ is equal to $sum d(u)/2$. I need the concept especialy of b) explained to me.

combinatorics discrete-mathematics graph-theory

share|cite|improve this question

edited Mar 26 at 16:26

Shubham Johri

5,668918

asked Mar 26 at 16:03

ChonChonChonChon

183

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I believe you meant there is a bijection between $V(L(G))$ and the set of edges of $G$.
  $endgroup$
  – Shubham Johri
  Mar 26 at 16:42
  

  
  
  
  

add a comment | 

$begingroup$

Having a problem that came up with using an old exercise book(so i have no solution to check or if is valid).

for a simple non-directed graph $G$ of order $n$ and size $m>1,L(G)$ (another graph) is defined as:

a)Every vertex of $L(G)$ is an edge of $G (1-1$ function)

b)$2$ vertices of $L(G)$ are connected by an edge iff the equivalent edges in $G$ have a common vertex

Prove that the number of edges of $L(G)$ $$sum_uin V(G)binomd(u)2$$(binomial coeficient).

My workprocess so far:By having a $1-1$ ratio of vertices $(L(G)$ - edges($G$) i can show that $n$ of $L(G)$ is equal to $sum d(u)/2$. I need the concept especialy of b) explained to me.

combinatorics discrete-mathematics graph-theory

share|cite|improve this question

edited Mar 26 at 16:26

Shubham Johri

5,668918

asked Mar 26 at 16:03

ChonChonChonChon

183

$endgroup$

share|cite|improve this question

edited Mar 26 at 16:26

Shubham Johri

5,668918

asked Mar 26 at 16:03

ChonChonChonChon

183

share|cite|improve this question

edited Mar 26 at 16:26

Shubham Johri

5,668918

asked Mar 26 at 16:03

ChonChonChonChon

183

edited Mar 26 at 16:26

Shubham Johri

5,668918

edited Mar 26 at 16:26

Shubham Johri

5,668918

asked Mar 26 at 16:03

ChonChonChonChon

183

asked Mar 26 at 16:03

ChonChonChonChon

183

2 Answers
2

active

oldest

votes

0

$begingroup$

So the degree of each vertex $e= x,y$ in $L(G)$ is $$d_L(e) = d(x)+d(y)-2$$

So by handshakeing lemma we have $$1over 2sum _x,yin Ed_L(x,y)= 1over 2sum _x,yin E (d(x)+d(y)-2)$$

Now since each $x$ appears in sum exactly $d(x)$ times we have:

$$1over 2Big(sum _xin V d(x)^2Big)-varepsilon ;;;(*) $$

By handshakeing lemma for the starting graph we have $$sum _xin V d(x)=2varepsilon $$

so we have $$ (*) = 1over 2Big(sum _xin V d(x)^2-d(x) Big) = sum _xin Vd(x)choose 2 $$

share|cite|improve this answer

answered Mar 26 at 16:32

Maria MazurMaria Mazur

50.2k1361126

$endgroup$

add a comment | 

0

$begingroup$

Consider $vin V(G)$.

If $d(v)le1$, $v$ doesn't contribute any edge to $L(G)$ because we need at-least two edges incident on $v$ for it to be their common vertex.

Whereas if $d(v)>1,v$ has $d(v)$ distinct edges incident on it. Selecting any two of these edges gives us an edge in $L(G)$. Recall that two edges can be selected in $binomd(v)2$ ways. We now sum this value over all the vertices of $G$.

Note that if $d(v)le1,binomd(v)2$ is assumed to be $0$.

share|cite|improve this answer

answered Mar 26 at 16:35

Shubham JohriShubham Johri

5,668918

$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
);



);

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

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3163383%2fnumber-of-edges-in-a-transformation-graph%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

So the degree of each vertex $e= x,y$ in $L(G)$ is $$d_L(e) = d(x)+d(y)-2$$

So by handshakeing lemma we have $$1over 2sum _x,yin Ed_L(x,y)= 1over 2sum _x,yin E (d(x)+d(y)-2)$$

Now since each $x$ appears in sum exactly $d(x)$ times we have:

$$1over 2Big(sum _xin V d(x)^2Big)-varepsilon ;;;(*) $$

By handshakeing lemma for the starting graph we have $$sum _xin V d(x)=2varepsilon $$

so we have $$ (*) = 1over 2Big(sum _xin V d(x)^2-d(x) Big) = sum _xin Vd(x)choose 2 $$

share|cite|improve this answer

answered Mar 26 at 16:32

Maria MazurMaria Mazur

50.2k1361126

$endgroup$

add a comment | 

0

$begingroup$

So the degree of each vertex $e= x,y$ in $L(G)$ is $$d_L(e) = d(x)+d(y)-2$$

So by handshakeing lemma we have $$1over 2sum _x,yin Ed_L(x,y)= 1over 2sum _x,yin E (d(x)+d(y)-2)$$

Now since each $x$ appears in sum exactly $d(x)$ times we have:

$$1over 2Big(sum _xin V d(x)^2Big)-varepsilon ;;;(*) $$

By handshakeing lemma for the starting graph we have $$sum _xin V d(x)=2varepsilon $$

so we have $$ (*) = 1over 2Big(sum _xin V d(x)^2-d(x) Big) = sum _xin Vd(x)choose 2 $$

share|cite|improve this answer

answered Mar 26 at 16:32

Maria MazurMaria Mazur

50.2k1361126

$endgroup$

add a comment | 

$begingroup$

So the degree of each vertex $e= x,y$ in $L(G)$ is $$d_L(e) = d(x)+d(y)-2$$

So by handshakeing lemma we have $$1over 2sum _x,yin Ed_L(x,y)= 1over 2sum _x,yin E (d(x)+d(y)-2)$$

Now since each $x$ appears in sum exactly $d(x)$ times we have:

$$1over 2Big(sum _xin V d(x)^2Big)-varepsilon ;;;(*) $$

By handshakeing lemma for the starting graph we have $$sum _xin V d(x)=2varepsilon $$

so we have $$ (*) = 1over 2Big(sum _xin V d(x)^2-d(x) Big) = sum _xin Vd(x)choose 2 $$

share|cite|improve this answer

answered Mar 26 at 16:32

Maria MazurMaria Mazur

50.2k1361126

$endgroup$

share|cite|improve this answer

answered Mar 26 at 16:32

Maria MazurMaria Mazur

50.2k1361126

answered Mar 26 at 16:32

Maria MazurMaria Mazur

50.2k1361126

answered Mar 26 at 16:32

Maria MazurMaria Mazur

50.2k1361126

0

$begingroup$

Consider $vin V(G)$.

If $d(v)le1$, $v$ doesn't contribute any edge to $L(G)$ because we need at-least two edges incident on $v$ for it to be their common vertex.

Whereas if $d(v)>1,v$ has $d(v)$ distinct edges incident on it. Selecting any two of these edges gives us an edge in $L(G)$. Recall that two edges can be selected in $binomd(v)2$ ways. We now sum this value over all the vertices of $G$.

Note that if $d(v)le1,binomd(v)2$ is assumed to be $0$.

share|cite|improve this answer

answered Mar 26 at 16:35

Shubham JohriShubham Johri

5,668918

$endgroup$

add a comment | 

0

$begingroup$

Consider $vin V(G)$.

If $d(v)le1$, $v$ doesn't contribute any edge to $L(G)$ because we need at-least two edges incident on $v$ for it to be their common vertex.

Whereas if $d(v)>1,v$ has $d(v)$ distinct edges incident on it. Selecting any two of these edges gives us an edge in $L(G)$. Recall that two edges can be selected in $binomd(v)2$ ways. We now sum this value over all the vertices of $G$.

Note that if $d(v)le1,binomd(v)2$ is assumed to be $0$.

share|cite|improve this answer

answered Mar 26 at 16:35

Shubham JohriShubham Johri

5,668918

$endgroup$

add a comment | 

$begingroup$

Consider $vin V(G)$.

If $d(v)le1$, $v$ doesn't contribute any edge to $L(G)$ because we need at-least two edges incident on $v$ for it to be their common vertex.

Whereas if $d(v)>1,v$ has $d(v)$ distinct edges incident on it. Selecting any two of these edges gives us an edge in $L(G)$. Recall that two edges can be selected in $binomd(v)2$ ways. We now sum this value over all the vertices of $G$.

Note that if $d(v)le1,binomd(v)2$ is assumed to be $0$.

share|cite|improve this answer

answered Mar 26 at 16:35

Shubham JohriShubham Johri

5,668918

$endgroup$

share|cite|improve this answer

answered Mar 26 at 16:35

Shubham JohriShubham Johri

5,668918

answered Mar 26 at 16:35

Shubham JohriShubham Johri

5,668918

answered Mar 26 at 16:35

Shubham JohriShubham Johri

5,668918