Prove the Number of Edges in Graph Theory

[twilit walrus]

1. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
2. Wait patiently for a helper to come along.
3. Once someone helps you, say thank you and close the thread with:

   +close
   

4. Feel free to nominate the person for helper of the week in #helper-nominations
5. Do not ping the mods, unless someone is breaking the rules.
6. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[dusky ether]

Given this question, how would I prove the number of edges?

Part 2 of this, sorry

So far, I have handshake lemma and binomial theorem but im having trouble trying to understand how to begin the proof

[versed compass]

Hm... Perhaps, it's possible to set up a recurrence relation?

If it will be a linear recurrence relation, solving it is very easy, as long as you know B1 (which you probably do).

[dusky ether]

i know how the graph of B1 looks. im not quite following with the recurrence relation however. can you elaborate?

[versed compass]

I don't really know graph theory, but what I meant is that, if possible, you can maybe relate B(n) to B(n - 1).

[dusky ether]

oh yeah i see what youre saying now. ive been trying to do that but its moreso following the logic to set up a recurrence relation which im stuck on

[versed compass]

Ah, I see... Well, maybe someone else knows how to do that.

[shut horizon]

suppose (d_k){k=1}^{n} is a binary string of length n. We want to find out how many edges are adjacent to it. We have this criterion for adjacency :
if (d_k){k=1}^n and (b_k)_{k=1}^n are adjacent then we may have these possible cases for each digit :
d_i = 1 = b_i
d_i = 1, b_i = 0
d_i = 0, b_i = 1
we see that when d_i is one we have two possible values for b_i. d_i is zero, b_i must be 1.
How many strings (b_k) can we make like this?
it's just 2^(number of ones in (d_k))

so the number of edges is :

oh wait

@frigid pond is 0(n-2 0's)1 considered a n-length string

a recurrence is the better way out obviously but this method seems more fun

[frigid pond]

Let's try with 3 bits:
000 -> 111
001 -> 110, 111
010 -> 101, 111
011 -> 100, 101, 110, 111
100 -> 011, 111
101 -> 010, 011, 110, 111
110 -> 001, 011, 101, 111
111 -> all 8

We have: 27, 26 without self-loops. Each edge is counted twice, so we have that, we get 13.
Which does match with (3^3 - 1)/2.

In general, you count the number of zeros (say k), and you get the complements, where the same k slots are 1's and the rest (n-k) are whatever (2^(n-k) possible choices).
For example, 001 begins with two zeros, so you know that the neighbors have a string that start with '11_', you just gotta fill the gap

So you count with respect to the number of zeros, from k = 0 to n : (n choose k) 2^(n-k)

Which is nothing but (1 + 2)^n

then substract 1 for the self-loop of 111...111

divide by 2, because we counted every other edge twice

so (3^n - 1)/2

pro gamer move

[frigid pond]

Yes

Ergo: induction is not necessary here

In the contrary I feel like using induction is more likely to screw things up

because you have one more bit

that adds a lot more edges and vertices

[shut horizon]

finding a recurrence isn't that bad too

[frigid pond]

in comparison to direct proof, it sounds a lot more tedious

since direct proof is a direct application of Newton's binomial formula