Graph Theory
No TL;DR found
Abstract
You are encouraged to work together on solving homework problems, but please put their names clearly at the top of the assignment. Everyone must turn in their own independently written solutions. Homework is due at the beginning of class. 1. Draw all non-isomorphic undirected (not necessarily simple) graphs on three vertices without loops and such that for every pair of distinct vertices there are at most two edges joining them. Mark connected graphs with " C " , Eulerean graphs 1 with " E " , and Hamiltonian graphs 2 with " H ". 2. Prove that the degree sequence does not uniquely determine if a graph is connected or not. In other words, construct two simple graphs G and H with the same degree sequence and such that G is connected whereas H is not. 3. Prove that an integer sequence (d 1 ,. .. , d n) is graphic if and only if the sequence 4. The n-cube graph Q n is the simple graph with V (Q n) def = {0, 1} n and such that (u, v) ∈ E(Q n) if and only if these strings differ in precisely one coordinate.