# Graph theory bipartite proofs with induction

I have this question I am given in a quiz and right away I did not even do it...I absolutely suck at induction as well as any kind of proofs. This question unfortunately had both...No matter what explanation I give for inductions I always get poor marks on it and 0s frequently.. Now worse comes graph theory which I barely understand or see any application for..

Anyhow I didnt do this question on the test or even try it, I dont know of when my answer is right or wrong anymore..Can someone try to make sense of this question?

-
It's hard to give advice when we don't know what you know. Do you know what a bipartite graph is? Do you understand what the vertex partition of a bipartite graph is? Do you know what a 103-regular graph is? – Gerry Myerson Mar 26 '12 at 5:22
I know what a vertex is, I know bipartite graph. The rest I dont know – Raynos Mar 26 '12 at 11:54
@Ranyos Whenever possible, especially in graph theory, try to understand the situation by drawing a diagram. In (i) you have to prove a property about bipartite graphs in general. So you could start by some small bipartite graph and see what is happening. – caffeinemachine Jul 23 '15 at 2:37

(i) In case you don't know what degree is, by your comments you do not, it is the number of edges incident to each vertex. So, a vertex of degree 3 has 3 edges extending from it. Since this is a bipartite graph, and since all the edges must have one end in $A$ and one end $B$, it is pretty clear that we will satisfy $\sum_{i \in A} d_i = \sum_{j \in B} d_j$, as each edge contributes one to each sum. And, we can prove it by induction.

Assume we have one edge. It must be between a vertex in $A$ and one in $B$ so the two sums of degrees are both 1, thus equal.

Assume for $|E| = k$, it is true that $\sum_{i \in A} d_i = \sum_{j \in B} d_j$. Consider a bipartite graph with $|E| = k + 1$. Delete one edge and we have a bipartite graph with $|E| = k$. Under our assumption, we have $\sum_{i \in A} d_i = \sum_{j \in B} d_j$ for this smaller graph. And, the one edge that we deleted will contribute 1 to each side of this, so we will still have equality when we add it back.

This proves it by induction. We know it is true for graph satisfying $|E| = 1$, and we also know that if it is true for any graph satisfying $|E| = k$, it must be true for any graph satisfying $|E| = k + 1$. The induction is that we know it's true for $|E| = 1$. Thus, it's true for $|E| = 2$. Thus, it's true for $|E| = 3$. Thus, it's true for $|E| = 4$, ..., forever.

(ii) A regular graph is one where all vertices have the same degree, so all vertices are incident to the same number of edges. A 103-regular graph is one where all vertices have 103 edges attached to them. The 103 is not necessary here. We can prove that for every regular bipartite graph (of any degree), $|A| = |B|$.

Assume $G$ is a regular bipartite graph. By (i), $\sum_{i \in A} d_i = \sum_{j \in B} d_j$. By our assumption of regular, all the $d_i$'s and $d_j$'s are the same. Let's call them all $d$ then (so this graph is $d$-regular, and what you are asked to prove is the special case $d = 103$). Thus, we have $$\sum_{i \in A} d = \sum_{j \in B} d$$ So, this takes $|A|$ occurrences of $d$ and adds them together on the left side, and $|B|$ occurrences of $d$ on the right side, so that $$d \cdot |A| = d \cdot |B|$$ Dividing both sides by $d$ we get $$|A| = |B|$$

-
i can usually understand the solution once i see it but when im on my own i cant get it :( dont know what to do – Raynos Mar 26 '12 at 13:34
@raynos If you don't understand induction, you should start on easier problems first. If you don't understand basic graph theory, get a pretty basic book and start reading and doing some easy problems. Math is hard for lots of people, not just you. Even people getting PhDs in math have trouble with math at times. You just work hard, read, think, take notes, do problems. It eventually starts making sense. – Graphth Mar 26 '12 at 14:24
@Graphth I would say that if you are getting PhD in math, it is the math that should cause troubles, otherwise the thesis is just trivial, isn't it? – dtldarek Mar 26 '12 at 23:19
@Graphth :In the question 1 for proving the n+1 case, Why is a edge from graph with n+1 edges is deleted first and then add it?Consider a bipartite graph with |E|=k+1. Delete one edge and we have a bipartite graph with |E|=k.Is it because our induction hypothesis is something like Let P(n) be the statement that for a bipartite graph with n edges $\sum_{i \in A} d_i = \sum_{j \in B} d_j$ is true.Then for the n+1 case we consider a bipartite graph with n+1 edges but our hypothesis holds for only a tree with n edges. – clarkson Oct 7 '14 at 9:36

The degree of vertex $i \in V$ is a number of edges adjacent to $i$. First question asks you to proof that the sum of degrees of all vertices from left side of the bipartite graph is equal to the sum of all degrees of all vertices from right side. The intuition is that every edge that starts in the left side has to end somewhere in the right side. Moreover the question asks you to do it by induction on the number of edges in the graph.

First show that if there are no edges in the graph then the equality holds (indeed $0 = 0$, doesn't it?). Then, assuming that for every graph with $n$ edges the equality is true, show that it is also true for every graph with $n+1$ edges (so we have a bipartite graph with $n+1$ edges, then remove any edge, the equality holds, so if you add the edge in question back, and the graph is bipartite, you add $1$ to both sides of the equation, so equality holds again).

A 103-regular graph is a graph where every vertex has degree of 103, i.e. every vertex has 103 adjacent edges. You need to show that if graph is $103$-regular, then $|A| = |B|$, that means the number of vertices on the left side is the same as in the right (the intuition is that if you have $n$ vertices on the left with degree of 103, then you have $103 n$ edges from left to right, and those edges have to end somewhere, and the vertices on the right side has degree of 103 too, so you need $\frac{103 n}{103}$ vertices on the right side).

This of course can be done by induction, but it is easier to show directly.

I didn't write the whole proof by intention, it is almost everything, but you should reformulate it into mathematical notation. Hope that solves your problem.

P.S. Considering the notation in the question I guess you deal with math or computer science. You have said that "Now worse comes graph theory which I barely [...] see any application for". I don't want to be rude, but if I were you I would force myself to learn to love graphs. Graphs are omnipresent in mathematics and in other domains too, you will meet them eating breakfast, driving work, learning, working, talking to people, shopping or flying, even your brain is a graph! Please, for you own good, work hard to understand the basics and even harder to see some applications (those are especially important)! On a happier note, graphs are (in some way) indeed beautiful, and believe me, knowing them you can appreciate how marvelous our world is even more. Good luck!

-
you sound just like my prof :P thanks I will try to force myself to believe they are useful :D :D :D – Raynos Mar 26 '12 at 13:25