minimal edge

Question

Question

Find a minimal edge coloring of the following graphs (color edges so that edges with a common end vertex receive different colors).

Answer 1

Answer #1

1.

if a is given red then b, c, d cannot be given red.

then, if b is given blue, then a, c, d cannot be blue.

a is red which is not blue.

giving c green then a, b, d cannot be green.

a, b are not green.

Hence, d cannot be red, blue or green.Hence, we assign it black.

We need minimum 4 colors to color this graph.

2.

It is a bi- paratite graph

Assign a red, then d, e, f cannot be red.

assign, d as blue now, a, b, c cannot be blue.

We can color b,c because they are not blue.

Similarly, e, f can be colored blue as it is not red.

We need minimum 2 colors to color this graph.

Add a comment

Answer 2

Similar Homework Help Questions

Find a minimal edge coloring of the following graphs ( color edges so that edges with...

Find a minimal edge coloring of the following graphs ( color edges so that edges with a common end vertex receive different colors).
A 2-coloring of an undirected graph with n vertices and m edges is the assignment of one of two colors (say, red or green) to each vertex of the graph

A 2-coloring of an undirected graph with n vertices and m edges is the assignment of one of two colors (say, red or green) to each vertex of the graph, so that no two adjacent nodes have the same color. So, if there is an edge (u,v) in the graph, either node u is red and v is green or vice versa. Give an O(n + m) time algorithm (pseudocode!) to 2-colour a graph or determine that no such coloring...
(2) Recall the following fact: In any planar graph, there exists a vertex whose degree is s 5 Use...

(2) Recall the following fact: In any planar graph, there exists a vertex whose degree is s 5 Use this fact to prove the six-color theorem: for any planar graph there exists a coloring with six colors, i.e. an assignment of six given colors (e.g. red, orange, yellow, green, blue, purple) to the vertices such that any two vertices connected by an edge have different colors. (Hint: use induction, and in the inductive step remove some verter and all edges...

(Applied Agebra) Edge Coloring Symmetry 6. To more formally describe the action of geometric symmetries on...

(Applied Agebra) Edge Coloring Symmetry 6. To more formally describe the action of geometric symmetries on edge colorings, we assume: Each symmetry is a permutation of the set of edges. . An edge coloring is a function whose donain is the set of edges and codomain is the set of available colors (informally, each edge gets assigned a color). For example, f(A-f(C) = BLUE. f(B) = RED gives the middle coloring of the triangle in the lecture notes, using edge...
B-1 Graph coloring Given an undirected graph G (V. E), a k-coloring of G is a function c : V → {0, 1, . . . ,k-1}

B-1 Graph coloring Given an undirected graph G (V. E), a k-coloring of G is a function c : V → {0, 1, . . . ,k-1} such that c(u)≠c(v) for every edge (u, v) ∈ E. In other words, the numbers 0.1,... k-1 represent the k colors, and adjacent vertices different colors. must havec. Let d be the maximum degree of any vertex in a graph G. Prove that we can color G with d +1 colors.
QUESTION 21 Suppose Prim's algorithm is being used find a minimal weight spanning tree for the...

QUESTION 21 Suppose Prim's algorithm is being used find a minimal weight spanning tree for the graph below. 4 B3 If C is the initial vertex, Give the vertex set and the edge set of the subtree after 3 iterations (at this point, your subtree should have 3 edges.)

Problem 2: Use gringo/clasp to determine whether the following graph can be colored with two colors...

Problem 2: Use gringo/clasp to determine whether the following graph can be colored with two colors so that no edge has both its endpoints colored with the same color, and if so, find at least one such coloring. Then, repeat the above assuming that three colors are available. More specifically, give propositional theories describing the two-coloring and the three-coloring problems for that graph, rewrite them into the gringo format, and run them through gringo/clasp 4
Consider the graph below. Use Prim's algorithm to find a minimal spanning tree of the graph rooted in vertex A.

Consider the graph below. Use Prim's algorithm to find a minimal spanning tree of the graph rooted in vertex A. Note: enter your answer as a set of edges [E1, E2, ...) and write each edge as a pair of nodes between parentheses separate by a comma and one blank space e.g. (A,B)
Question 1: Given an undirected connected graph so that every edge belongs to at least one...

Question 1: Given an undirected connected graph so that every edge belongs to at least one simple cycle (a cycle is simple if be vertex appears more than once). Show that we can give a direction to every edge so that the graph will be strongly connected. Question 2: Given a graph G(V, E) a set I is an independent set if for every uv el, u #v, uv & E. A Matching is a collection of edges {ei} so...

X) (4 points) If k is a positive integer, a k-coloring of a graph G is an assignment of one of k ...

COMP Discrete Structures: Please answer completely and clearly. (3). (5). x) (4 points) If k is a positive integer, a k-coloring of a graph G is an assignment of one of k possible colors to each of the vertices/edges of G so that adjacent vertices/edges have different colors. Draw pictures of each of the following (a) A 4-coloring of the edges of the Petersen graph. (b) A 3-coloring of the vertices of the Petersen graph. (e) A 2-coloring (d) A...