graph theory question.

Since each edge increases the sum of the degrees of the vertices by two, the number of vertices of odd degree must be even.

The connected graph could be a single tree, with two major subtrees of the even and odd numbers, such that the nth edge is is the sum of the (n-1)th edge and 2.

Then, if n is odd, the odd subtree would contain (n-1)/2+1 nodes and the even subtree contains (n-1)/2 nodes If n is even, the number of nodes on the odd and even subtrees would reverse.

Rap

Rap,

One or both of us has misinterpreted the problem. I think he's talking about the number of edges coming out of a given vertex being even or odd.

Mark

mark2

I was thinking of n nodes. My spanning tree would have that. If n is odd then the number of nodes on the odd subtree would be (n-1)/2+1 and the even subtree would be (n-1)/2.

Granted the edge degree of all the nodes, with the exception of the topmost one, would be three (n-2, 2, & n). The topmost node would have degree 2 for odd and even.

But then there's always the possibility that I can be barking up the wrong subtrees.

Rap

mark2

I was thinking of n nodes. My spanning tree would have that. If n is odd then the number of nodes on the odd subtree would be (n-1)/2+1 and the even subtree would be (n-1)/2.

Granted the edge degree of all the nodes, with the exception of the topmost one, would be three (n-2, 2, & n). The topmost node would have degree 2 for odd and even.

But then there's always the possibility that I can be barking up the wrong subtrees.

Rap

mark2

I was thinking of n nodes. My spanning tree would have that. If n is odd then the number of nodes on the odd subtree would be (n-1)/2+1 and the even subtree would be (n-1)/2.

Granted the edge degree of all the nodes, with the exception of the topmost one, would be three (n-2, 2, & n). The topmost node would have degree 2 for odd and even.

But then there's always the possibility that I can be barking up the wrong subtrees.

Rap

Thanks for the help
In our group, we created cases where m=0, l=0, l was odd and l was even. Using these 4 cases, we showed that in each case they result was connected using complete graphs and complete bipartite graphs.