Question

Given an undirected graph, its degree sequence is the monotonic non increasing sequence of the degrees of the vertices of the graph. For example, the cycle C4 has the degree sequence 2, 2, 2, 2 and the wheel W4 has the degree sequence 4,3,3,3,3. (a). What is the degree sequence of the complete bipartite graph Km,n, where m and n are positive integers? Briefly justify. (b). Provide a counter example to the following statement: If two simple undirected graphs have the same degree sequence, then they are isomorphic.

Answer 1

The degree sequence of a complete bipartite graph Km,n consists of m vertices with degree n and n vertices with degree m. A star graph S4 and a path graph P4 both have the same degree sequence but are not isomorphic, serving as a counter example that identical degree sequences imply isomorphism.

Step-by-step explanation:

The degree sequence of the complete bipartite graph Km,n, with partite sets of size m and n, consists of m vertices each with degree n, and n vertices each with degree m. This is because every vertex in one partite set is connected to every vertex in the other set and there are no edges within a partite set itself. Therefore, the degree of each vertex in one partite set is equal to the number of vertices in the opposite partite set.

As a counter example to the statement "If two simple undirected graphs have the same degree sequence, then they are isomorphic," consider the following: The star graph S4 with degree sequence 1, 1, 1, 3, and the path graph P4 with the same degree sequence. Despite having identical degree sequences, these two graphs are not isomorphic because their structural properties are different: S4 has a central vertex connected to all others, while P4 is a linear sequence of vertices.