7.3k views
1 vote
1. Can a simple directed graph G = (V.E) with at least three vertices and the property that degt (v) + deg (v) = 1, Wv € V exist or not? Show an example of such a graph if it exists or explain why it cannot exist. 2. Is a four-dimensional hypercube bipartite? If yes, show the blue-red coloring of the nodes. Otherwise, explain why the graph is not bipartite. 3. What is the sum of the entries in a row of the adjacency matrix for a pseudograph (where multiple edges and loops are allowed)? 4. Determine whether the given pair of graphs is isomorphic. Exhibit an isomorphism or provide a rigorous argument that none exists.

1 Answer

4 votes

Answer:

Such a simple directed graph cannot exist.

Proof by contradiction: Assume there exists a simple directed graph G = (V, E) with at least three vertices and the property that deg+(v) + deg-(v) = 1 for all v ∈ V. Let u, v, w be distinct vertices of G. Without loss of generality, assume there exists an edge u → v in E. There are two cases to consider:

Case 1: There exists an edge v → w in E. Then deg+(v) ≥ 1 and deg-(v) ≥ 1, which implies deg+(v) + deg-(v) ≥ 2. This contradicts the property that deg+(v) + deg-(v) = 1.

Case 2: There does not exist an edge v → w in E. Then any path from u to w must contain u → v and then exit v via an incoming edge. Thus, there exists an incoming edge to v and a path from v to w, which implies deg+(v) ≥ 1 and deg-(v) ≥ 1. Again, this contradicts the property that deg+(v) + deg-(v) = 1.

Therefore, our assumption leads to a contradiction, and the simple directed graph G cannot exist.

Yes, a four-dimensional hypercube is bipartite.

A four-dimensional hypercube, denoted Q4, is a graph with 16 vertices that can be obtained by taking the Cartesian product of two copies of the complete graph on two vertices, denoted K2. That is, Q4 = K2 x K2 x K2 x K2.

To show that Q4 is bipartite, we can color the vertices of Q4 in blue and red according to their binary representations. Specifically, we can assign the color blue to vertices whose binary representation has an even number of 1's, and red to vertices whose binary representation has an odd number of 1's. This gives us a proper 2-coloring of Q4, which proves that Q4 is bipartite.

The sum of the entries in a row of the adjacency matrix for a pseudograph is equal to the degree of the corresponding vertex.

In a pseudograph, multiple edges and loops are allowed, which means that a vertex may be incident to multiple edges that connect it to the same vertex, or it may have a loop that connects it to itself.

Step-by-step explanation:

User Oleg Dulin
by
7.7k points