- Is there a simple graph of 9 vertices with degree sequence 3, 3, 3, 3, 5, 6, 6, 6, 6?
- Is there a bipartite graph of 8 vertices with degrees 3, 3, 3, 5, 6, 6, 6, 6?
- In a simple graph with at least two vertices, show that there are at least two vertices with the same degree.
- A
**directed graph** (or **digraph**) is a graph X together with a function assigning to each edge, an **ordered pair** of vertices. The first vertex is called the **tail **of the edge and the second is called the **head. **To each vertex, v, we let be the number of the edges for which v is the tail and the number for which it is the head. We call the **outdegree** and the **indegree **of v. Prove that where the sum is over the vertex set of X.
- In any digraph, we define a
**walk **as a sequence with the tail of and its head. The analogous notions of trail, path, circuit, and cycle are easily extended to digraphs in the obvious way. If X is a digraph such that the outdegree of every vertex is at least one, show that X contains a cycle.

More later,

Nalin Pithwa

### Like this:

Like Loading...

*Related*