Graph types

Graphs: 

Zeph Grunschlag Copyright © Zeph Grunschlag, 2001-2002. Graphs

Agenda –Graphs : 

Agenda –Graphs L23 2 Graph basics and definitions Vertices/nodes, edges, adjacency, incidence Degree, in-degree, out-degree Degree, in-degree, out-degree Subgraphs, unions, isomorphism Adjacency matrices Types of Graphs Trees Undirected graphs Simple graphs, Multigraphs, Pseudographs Digraphs, Directed multigraph Bipartite Complete graphs, cycles, wheels, cubes, complete bipartite

Uses of Graph Theory in CS: 

Uses of Graph Theory in CS L23 3 Car navigation system Efficient database Build a bot to retrieve info off WWW Representing computational models Many other applications. This course we focus more on the properties of abstract graphs rather on algorithms (3137 has the algorithmics)

Graphs –Intuitive Notion: 

Graphs –Intuitive Notion L23 4 A graph is a bunch of vertices (or nodes) represented by circles which are connected by edges, represented by line segments . Mathematically, graphs are binary-relations on their vertex set (except for multigraphs). In Data Structures one often starts with trees and generalizes to graphs. In this course, opposite approach: We start with graphs and restrict to get trees.

Trees: 

Trees L23 5 A very important type of graph in CS is called a tree : Real Tree

Trees: 

Trees L23 6 A very important type of graph in CS is called a tree : Real Tree transformation

Trees: 

Trees L23 7 A very important type of graph in CS is called a tree : Real Tree transformation

Trees: 

Trees L23 8 A very important type of graph in CS is called a tree : Real Abstract Tree Tree transformation

Simple Graphs: 

Simple Graphs L23 9 Different purposes require different types of graphs. EG: Suppose a local computer network Is bidirectional (undirected) Has no loops (no “self-communication”) Has unique connections between computers Sensible to represent as follows:

Simple Graphs: 

Simple Graphs L23 10 Vertices are labeled to associate with particular computers Each edge can be viewed as the set of its two endpoints 1 2 3 4 {1,2} {3,4} {2,4} {1,3} {2,3} {1,4}

Simple Graphs: 

Simple Graphs L23 11 DEF: A simple graph G = ( V,E ) consists of a non-empty set V of vertices (or nodes ) and a set E (possibly empty) of edges where each edge is a subset of V with cardinality 2 (an unordered pair). Q: For a set V with n elements, how many possible edges there?

Simple Graphs: 

Simple Graphs L23 12 A: The number of pairs in V = C ( n ,2) = n · ( n -1) / 2 Q: How many possible graphs are there for the same set of vertices V ?

Simple Graphs: 

Simple Graphs L23 13 A: The number of subsets in the set of possible edges. There are n · ( n -1) / 2 possible edges, therefore the number of graphs on V is 2 n ( n -1)/2

Multigraphs: 

Multigraphs L23 14 If computers are connected via internet instead of directly, there may be several routes to choose from for each connection. Depending on traffic, one route could be better than another. Makes sense to allow multiple edges, but still no self-loops:

Multigraphs: 

Multigraphs L23 15 Edge-labels distinguish between edges sharing same endpoints. Labeling can be thought of as function: e 1  {1,2}, e 2  {1,2}, e 3  {1,3}, e 4  {2,3}, e 5  {2,3}, e 6  {1,2} 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6

Multigraphs: 

Multigraphs L23 16 DEF: A multigraph G = ( V,E,f ) consists of a non-empty set V of vertices (or nodes ), a set E (possibly empty) of edges and a function f with domain E and codomain the set of pairs in V .

Pseudographs: 

Pseudographs L23 17 If self-loops are allowed we get a pseudograph: Now edges may be associated with a single vertex, when the edge is a loop e 1  {1,2}, e 2  {1,2}, e 3  {1,3}, e 4  {2,3}, e 5  {2}, e 6  {2}, e 7  {4} 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6 e 7

Multigraphs: 

Multigraphs L23 18 DEF: A pseudograph G = ( V,E,f ) consists of a non-empty set V of vertices (or nodes ), a set E (possibly empty) of edges and a function f with domain E and codomain the set of pairs and singletons in V .

Undirected Graphs Terminology: 

Undirected Graphs Terminology L23 19 Vertices are adjacent if they are the endpoints of the same edge. Q: Which vertices are adjacent to 1? How about adjacent to 2, 3, and 4? 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6

Undirected Graphs Terminology: 

Undirected Graphs Terminology L23 20 A: 1 is adjacent to 2 and 3 2 is adjacent to 1 and 3 3 is adjacent to 1 and 2 4 is not adjacent to any vertex 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6

Undirected Graphs Terminology: 

Undirected Graphs Terminology L23 21 A vertex is incident with an edge (and the edge is incident with the vertex) if it is the endpoint of the edge. Q: Which edges are incident to 1? How about incident to 2, 3, and 4? 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6

Undirected Graphs Terminology: 

Undirected Graphs Terminology L23 22 A: e 1 , e 2 , e 3 , e 6 are incident with 2 2 is incident with e 1 , e 2 , e 4 , e 5 , e 6 3 is incident with e 3 , e 4 , e 5 4 is not incident with any edge 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6

Digraphs: 

Digraphs L23 23 Last time introduced digraphs as a way of representing relations: Q: What type of pair should each edge be (multiple edges not allowed)? 1 2 3 4

Digraphs: 

Digraphs L23 24 A: Each edge is directed so an ordered pair (or tuple) rather than unordered pair. Thus the set of edges E is just the represented relation on V . 1 2 3 4 (1,2) (1,1) (2,2) (2,4) (1,3) (2,3) (3,4) (3,3) (4,4)

Digraphs: 

Digraphs L23 25 DEF: A directed graph (or digraph ) G = ( V,E ) consists of a non-empty set V of vertices (or nodes ) and a set E of edges with E  V  V . The edge ( a,b ) is also denoted by a  b and a is called the source of the edge while b is called the target of the edge. Q: For a set V with n elements, how many possible digraphs are there?

Digraphs: 

Digraphs L23 26 A: The same as the number of relations on V , which is the number of subsets of V  V so 2 n · n .

Directed Multigraphs: 

Directed Multigraphs L23 27 If also want to allow multiple edges in a digraph, get a directed multigraph (or multi-digraph ). Q: How to use sets and functions to deal with multiple directed edges, loops? 1 2 3

Directed Multigraphs: 

Directed Multigraphs L23 28 A: Have function with domain the edge set and codomain V  V . e 1  (1,2), e 2  (1,2), e 3  (2,2), e 4  ( 2,3), e 5  (2,3), e 6  (3,3), e 7  (3,3) 1 2 3 e 1 e 3 e 2 e 4 e 5 e 7 e 6

Degree: 

Degree L23 29 The degree of a vertex counts the number of edges that seem to be sticking out if you looked under a magnifying glass: 1 2 3 e 1 e 3 e 2 e 4 e 5 e 6

Degree: 

Degree L23 30 The degree of a vertex counts the number of edges that seem to be sticking out if you looked under a magnifying glass: 1 2 3 e 1 e 3 e 2 e 4 e 5 e 6 magnify

Degree: 

Degree L23 31 The degree of a vertex counts the number of edges that seem to be sticking out if you looked under a magnifying glass: Thus deg(2) = 7 even though 2 only incident with 5 edges. Q: How to define this formally? 1 2 3 e 1 e 3 e 2 e 4 e 5 e 6 magnify

Degree: 

Degree L23 32 A: Add 1 for every regular edge incident with vertex and 2 for every loop. Thus deg(2) = 1 + 1 + 1 + 2 + 2 = 7 1 2 3 e 1 e 3 e 2 e 4 e 5 e 6 magnify

Oriented Degree when Edges Directed: 

Oriented Degree when Edges Directed L23 33 The in-degree of a vertex (deg - ) counts the number of edges that stick in to the vertex. The out-degree (deg + ) counts the number sticking out . Q: What are in-degrees and out-degrees of all the vertices? 1 2 3

Oriented Degree when Edges Directed: 

Oriented Degree when Edges Directed L23 34 A: deg - (1) = 0 deg - (2) = 3 deg - (3) = 4 deg + (1) = 2 deg + (2) = 3 deg + (3) = 2 1 2 3

Handshaking Theorem: 

Handshaking Theorem L23 35 There are two ways to count the number of edges in the above graph: Just count the set of edges: 7 Count seeming edges vertex by vertex and divide by 2 because double-counted edges: ( deg(1)+deg(2)+deg(3)+deg(4) )/2 = (3+7+2+2)/2 = 14/2 = 7 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6 e 7

Handshaking Theorem: 

Handshaking Theorem L23 36 THM: In an undirected graph In a directed graph Q: In a party of 5 people can each person be friends with exactly three others?

Handshaking Theorem: 

Handshaking Theorem L23 37 A: Imagine a simple graph with 5 people as vertices and edges being undirected edges between friends (simple graph assuming friendship is symmetric and irreflexive). Number of friends each person has is the degree of the person. Handshaking would imply that | E | = (sum of degrees)/2 or 2| E | = (sum of degrees) = (5·3) = 15. Impossible as 15 is not even. In general:

Handshaking Theorem: 

Handshaking Theorem L23 38 Lemma: The number of vertices of odd degree must be even in an undirected graph. Proof : Otherwise would have 2| E | = Sum of even no.’s + an odd number of odd no.’s even = even + odd –this is impossible. 

Graph Patterns Complete Graphs - Kn: 

Graph Patterns Complete Graphs - K n L23 39 A simple graph is complete if every pair of distinct vertices share an edge. The notation K n denotes the complete graph on n vertices. K 1 K 2 K 3 K 4 K 5

Graph Patterns Cycles - Cn: 

Graph Patterns Cycles - C n L23 40 The cycle graph C n is a circular graph with V = {0,1,2,…, n -1} where vertex i is connected to i +1 mod n and to i -1 mod n . They look like polygons: C 1 C 2 C 3 C 4 C 5 Q: What type of graph are C 1 and C 2 ?

Graph Patterns Wheels - Wn : 

Graph Patterns Wheels - W n L23 41 A: Pseudographs The wheel graph W n is just a cycle graph with an extra vertex in the middle: W 1 W 2 W 3 W 4 W 5 Usually consider wheels with 3 or more spokes only.

Graph Patterns Cubes - Qn: 

Graph Patterns Cubes - Q n L23 42 The n -cube Q n is defined recursively. Q 0 is just a vertex. Q n +1 is gotten by taking 2 copies of Q n and joining each vertex v of Q n with its copy v’ : Q 0 Q 1 Q 2 Q 3 Q 4 (hypercube)

Bipartite Graphs: 

Bipartite Graphs L23 43 A simple graph is bipartite if V can be partitioned into V = V 1  V 2 so that any two adjacent vertices are in different parts of the partition. Another way of expressing the same idea is bichromatic : vertices can be colored using two colors so that no two vertices of the same color are adjacent.

Bipartite Graphs: 

Bipartite Graphs L23 44 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 45 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 46 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 47 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 48 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 49 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 50 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 51 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 52 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 53 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 54 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it:

Bipartite Graphs: 

Bipartite Graphs L23 55 EG: C 4 is a bichromatic: And so is bipartite, if we redraw it: Q: For which n is C n bipartite?

Bipartite Graphs: 

Bipartite Graphs L23 56 A: C n is bipartite when n is even. For even n color all odd numbers red and all even numbers green so that vertices are only adjacent to opposite color. If n is odd, C n is not bipartite. If it were, color 0 red. So 1 must be green, and 2 must be red. This way, all even numbers must be red, including vertex n -1. But n -1 connects to 0 .

Graph Patterns Complete Bipartite - Km,n : 

Graph Patterns Complete Bipartite - K m,n L23 57 When all possible edges exist in a simple bipartite graph with m red vertices and n green vertices, the graph is called complete bipartite and the notation K m,n is used. EG: K 2,3 K 4,5

Subgraphs : 

Subgraphs L23 58 Notice that the 2-cube occurs inside the 3-cube . In other words, Q 2 is a subgraph of Q 3 : DEF: Let G = ( V,E ) and H = ( W,F ) be graphs. H is said to be a subgraph of G , if W  V and F  E . Q: How many Q 2 subgraphs does Q 3 have?

Subgraphs: 

Subgraphs L23 59 A: Each face of Q 3 is a Q 2 subgraph so the answer is 6, as this is the number of faces on a 3-cube:

Unions: 

Unions L23 60 In previous example can actually reconstruct the 3-cube from its 6 2-cube faces:

Unions: 

Unions L23 61 If we assign the 2-cube faces (aka S quares) the names S 1 , S 2 , S 3 , S 4 , S 5 , S 6 then Q 3 is the union of its faces: Q 3 = S 1  S 2  S 3  S 4  S 5  S 6

Unions: 

Unions L23 62 DEF: Let G 1 = ( V 1 , E 1 ) and G 2 = ( V 2 , E 2 ) be two simple graphs (and V 1 , V 2 may or may not be disjoint). The union of G 1 , G 2 is formed by taking the union of the vertices and edges. I.E: G 1  G 2 = ( V 1  V 2 , E 1  E 2 ). A similar definitions can be created for unions of digraphs, multigraphs, pseudographs, etc.

Adjacency Matrix: 

Adjacency Matrix L23 63 We already saw a way of representing relations on a set with a Boolean matrix: R digraph( R ) M R 1 1 2 2 3 3 4 4 1 2 3 4

Adjacency Matrix: 

Adjacency Matrix L23 64 Since digraphs are relations on their vertex sets, can adopt the concept to represent digraphs. In the context of graphs, we call the representation an adjacency matrix : For a digraph G = ( V,E ) define matrix A G by: Rows, Columns –one for each vertex in V Value at i th row and j th column is 1 if i th vertex connects to j th vertex ( i  j ) 0 otherwise

Adjacency Matrix -Directed Multigraphs: 

Adjacency Matrix -Directed Multigraphs L23 65 Can easily generalize to directed multigraphs by putting in the number of edges between vertices, instead of only allowing 0 and 1: For a directed multigraph G = ( V,E ) define the matrix A G by: Rows, Columns –one for each vertex in V Value at i th row and j th column is The number of edges with source the i th vertex and target the j th vertex

Adjacency Matrix -Directed Multigraphs: 

Adjacency Matrix -Directed Multigraphs L23 66 Q: What is the adjacency matrix? 1 2 3 4

Adjacency Matrix -Directed Multigraphs: 

Adjacency Matrix -Directed Multigraphs L23 67 A: 1 2 3 4

Adjacency Matrix -General: 

Adjacency Matrix -General L23 68 Undirected graphs can be viewed as directed graphs by turning each undirected edge into two oppositely oriented directed edges, except when the edge is a self-loop in which case only 1 directed edge is introduced. EG: 1 2 3 4 1 2 3 4

Adjacency Matrix -General: 

Adjacency Matrix -General L23 69 Q: What’s the adjacency matrix? 1 2 3 4

Adjacency Matrix -General: 

Adjacency Matrix -General L23 70 A: Notice that answer is symmetric . 1 2 3 4

Adjacency Matrix -General: 

Adjacency Matrix -General L23 71 For an undirected graph G = ( V,E ) define the matrix A G by: Rows, Columns –one for each element of V Value at i th row and j th column is the number of edges incident with vertices i and j . This is equivalent to converting first to a directed graph as above. Or by allowing undirected edges to take us from i to j can simply use definition for directed graphs.

Graph Isomorphism: 

Graph Isomorphism L23 72 Various mathematical notions come with their own concept of equivalence , as opposed to equality: Equivalence for sets is bijectivity: EG { , , }  {12, 23, 43} Equivalence for graphs is isomorphism: EG 

Graph Isomorphism: 

Graph Isomorphism L23 73 Intuitively, two graphs are isomorphic if can bend, stretch and reposition vertices of the first graph, until the second graph is formed. Etymologically, isomorphic means “same shape”. EG: Can twist or relabel: to obtain:

Graph Isomorphism Undirected Graphs: 

Graph Isomorphism Undirected Graphs L23 74 DEF: Suppose G 1 = ( V 1 , E 1 ) and G 2 = ( V 2 , E 2 ) are pseudographs. Let f : V 1  V 2 be a function s.t.: f is bijective for all vertices u,v in V 1 , the number of edges between u and v in G 1 is the same as the number of edges between f ( u ) and f ( v ) in G 2 . Then f is called an isomorphism and G 1 is said to be isomorphic to G 2 .

Graph Isomorphism Digraphs: 

Graph Isomorphism Digraphs L23 75 DEF: Suppose G 1 = ( V 1 , E 1 ) and G 2 = ( V 2 , E 2 ) are directed multigraphs. Let f : V 1  V 2 be a function s.t.: f is bijective for all vertices u,v in V 1 , the number of edges from u to v in G 1 is the same as the number of edges between f ( u ) and f ( v ) in G 2 . Then f is called an isomorphism and G 1 is said to be isomorphic to G 2 . Note: Only difference between two definitions is the italicized “from” in no. 2 (was “between”).

Graph Isomorphism -Example: 

Graph Isomorphism -Example L23 76 EG: Prove that is isomorphic to . First label the vertices: 1 2 3 5 4 1 2 3 5 4

Graph Isomorphism -Example: 

Graph Isomorphism -Example L23 77 Next, set f (1) = 1 and try to walk around clockwise on the star. 1 2 3 5 4 1 2 3 5 4

Graph Isomorphism -Example: 

Graph Isomorphism -Example L23 78 Next, set f (1) = 1 and try to walk around clockwise on the star. The next vertex seen is 3, not 2 so set f (2) = 3. 2 3 5 4 2 3 5 4 1 1

Graph Isomorphism -Example: 

Graph Isomorphism -Example L23 79 Next, set f (1) = 1 and try to walk around clockwise on the star. The next vertex seen is 3, not 2 so set f (2) = 3. Next vertex is 5 so set f (3) = 5. 3 5 4 2 5 4 2 3 1 1

Graph Isomorphism -Example: 

Graph Isomorphism -Example L23 80 Next, set f (1) = 1 and try to walk around clockwise on the star. The next vertex seen is 3, not 2 so set f (2) = 3. Next vertex is 5 so set f (3) = 5. In this fashion we get f (4) = 2 5 4 2 4 3 5 2 3 1 1

Graph Isomorphism -Example: 

Graph Isomorphism -Example L23 81 Next, set f (1) = 1 and try to walk around clockwise on the star. The next vertex seen is 3, not 2 so set f (2) = 3. Next vertex is 5 so set f (3) = 5. In this fashion we get f (4) = 2, f (5) = 4. 4 2 3 5 2 3 1 1 5 4

Graph Isomorphism -Example: 

Graph Isomorphism -Example L23 82 Next, set f (1) = 1 and try to walk around clockwise on the star. The next vertex seen is 3, not 2 so set f (2) = 3. Next vertex is 5 so set f (3) = 5. In this fashion we get f (4) = 2, f (5) = 4. If we would continue, we would get back to f (1) =1 so this process is well defined and f is a morphism. 1 2 3 5 4 1 2 3 5 4

Graph Isomorphism -Example: 

Graph Isomorphism -Example L23 83 Next, set f (1) = 1 and try to walk around clockwise on the star. The next vertex seen is 3, not 2 so set f (2) = 3. Next vertex is 5 so set f (3) = 5. In this fashion we get f (4) = 2, f (5) = 4. If we would continue, we would get back to f (1) =1 so this process is well defined and f is a morphism. Finally since f is bijective, f is an isomorphism. 1 2 3 5 4 1 2 3 5 4

Properties of Isomorphims: 

Properties of Isomorphims L23 84 Since graphs are completely defined by their vertex sets and the number of edges between each pair, isomorphic graphs must have the same intrinsic properties. I.e. isomorphic graphs have the same… …number of vertices and edges …degrees at corresponding vertices …types of possible subgraphs …any other property defined in terms of the basic graph theoretic building blocks!

Graph Isomorphism -Negative Examples: 

Graph Isomorphism -Negative Examples L23 85 Once you see that graphs are isomorphic, easy to prove it. Proving the opposite, is usually more difficult. To show that two graphs are non-isomorphic need to show that no function can exist that satisfies defining properties of isomorphism. In practice, you try to find some intrinsic property that differs between the 2 graphs in question.

Graph Isomorphism -Negative Examples: 

Graph Isomorphism -Negative Examples L23 86 A: Why are the following non-isomorphic? u 1 u 2 u 3 u 5 u 4 v 1 v 2 v 3 v 4

Graph Isomorphism -Negative Examples: 

Graph Isomorphism -Negative Examples L23 87 A: 1 st graph has more vertices than 2 nd . Q: Why are the following non-isomorphic? u 1 u 2 u 3 u 5 u 4 v 1 v 2 v 3 v 5 v 4

Graph Isomorphism -Negative Examples: 

Graph Isomorphism -Negative Examples L23 88 A: 1 st graph has more edges than 2 nd . Q: Why are the following non-isomorphic? u 1 u 2 u 3 u 5 u 4 v 1 v 2 v 3 v 5 v 4

Graph Isomorphism -Negative Examples: 

Graph Isomorphism -Negative Examples L23 89 A: 2 nd graph has vertex of degree 1, 1 st graph doesn't. Q: Why are the following non-isomorphic? u 1 u 2 u 3 u 6 u 4 u 5 u 7 u 9 v 1 v 2 v 3 v 6 v 4 v 5 v 7 v 8 v 9 u 8

Graph Isomorphism -Negative Examples: 

Graph Isomorphism -Negative Examples L23 90 A: 1 st graph has 2 degree 1 vertices, 4 degree 2 vertex and 2 degree 3 vertices. 2 nd graph has 3 degree 1 vertices, 3 degree 2 vertex and 3 degree 3 vertices. Q: Why are the following non-isomorphic? u 1 u 2 u 3 u 6 u 4 u 5 u 7 u 8 v 1 v 2 v 3 v 6 v 4 v 5 v 7 v 8

Graph Isomorphism -Negative Examples: 

Graph Isomorphism -Negative Examples L23 91 A: None of the previous approaches work as there are the same no. of vertices, edges, and same no. of vertices per degree. LEMMA: If G and H are isomorphic, then any subgraph of G will be isomorphic to some subgraph of H . Q: Find a subgraph of 2 nd graph which isn’t a subgraph of 1 st graph. u 1 u 2 u 3 u 6 u 4 u 5 u 7 u 8 v 1 v 2 v 3 v 6 v 4 v 5 v 7 v 8

Graph Isomorphism -Negative Examples: 

Graph Isomorphism -Negative Examples L23 92 A: This subgraph is not a subgraph of the left graph. Why not? Deg. 3 vertices must map to deg. 3 vertices. Since subgraph and left graph are symmetric, can assume v 2 maps to u 2 . Adjacent deg. 1 vertices to v 2 must map to degree 1 vertices, forcing the deg. 2 adjacent vertex v 3 to map to u 3 . This forces the other vertex adjacent to v 3 , namely v 4 to map to u 4 . But then a deg. 3 vertex has mapped to a deg. 2 vertex   u 1 u 2 u 3 u 6 u 4 u 5 u 7 u 8 v 1 v 2 v 3 v 6 v 4 v 5 v 7 v 8

Blackboard Exercise: 

Blackboard Exercise L23 93 Show that W 6 is not bipartite.