Characterizing Possible Sequences for Forests | Graph Theory Homework Question

Click For Summary
SUMMARY

The discussion focuses on characterizing degree sequences for forests in graph theory. A sequence d1, d2, ..., dn is a valid degree sequence for a forest if and only if the sum of the degrees equals 2n - k, where k represents the number of trees in the forest. This is analogous to the condition for trees, which requires the sum of the degrees to equal 2n - 2. The conversation emphasizes the need to establish a clear relationship between degree sequences and the structure of forests.

PREREQUISITES
  • Understanding of graph theory concepts, specifically degree sequences.
  • Familiarity with trees and forests in graph structures.
  • Knowledge of mathematical proofs and logic.
  • Basic skills in combinatorial mathematics.
NEXT STEPS
  • Research the properties of degree sequences in graph theory.
  • Study the differences between trees and forests in graph structures.
  • Learn about combinatorial proofs related to graph degree sequences.
  • Explore applications of degree sequences in network theory.
USEFUL FOR

Students and researchers in mathematics, particularly those focusing on graph theory, as well as educators looking to deepen their understanding of forest structures and degree sequences.

roadrunner
Messages
101
Reaction score
0

Homework Statement



Characterize all possible sequences d1; d2; : : : ; dn so that there exists a forest
with vertex set fv1; v2; : : : vng with deg(vi) = di. (So, you should nd a statement of the
form: a sequence d1; : : : dn comes from a forest if and only if ... )


I emailed him and asked...he said this

In the last homework, you proved that a sequence d1, d2, .. dn is the
degree sequence of a tree if and only if d1..dn are positive integers
and they sum to 2n-2.

I want you to prove a similar thing for forests. So you should show that
a sequence d1, d2, .. dn is the degree sequence of a tree if and only if

The Attempt at a Solution



Not too sure what I need to do?
 
Physics news on Phys.org
bump?
 

Similar threads

Combinatorics, Assigning Occurrence Numbers to Integers
  • · Replies 2 ·
Replies
2
Views
2K
Graph Theory: Extremal Problem
  • · Replies 1 ·
Replies
1
Views
2K
Graph Theory Proof: Prove All Vertices of Kn Have deg(v)=(n-1)
  • · Replies 3 ·
Replies
3
Views
2K
Euler circuit in a directed multigraph
  • · Replies 2 ·
Replies
2
Views
5K
Graph Theory: Prove Tree Has No Cycles & Adding Edge Creates Cycle
  • · Replies 1 ·
Replies
1
Views
4K
Proving a Tree is a Minimally Connected Graph in Graph Theory
  • · Replies 22 ·
Replies
22
Views
4K
How can the sequence of tasks be represented in a graph using only 6 nodes?
  • · Replies 2 ·
Replies
2
Views
3K
Proving a Cycle Exists in Finite Graphs with Degree 2+ Vertices
  • · Replies 4 ·
Replies
4
Views
2K
A tree with at least 2 vertices has at least 2 leaves
  • · Replies 1 ·
Replies
1
Views
5K
Proof about isomorphism (Graph Theory)
  • · Replies 3 ·
Replies
3
Views
2K