Graph Theory Lessons

Answers to Lesson 4

The relation S is reflexive. To prove this we have to show that if we have a graph G, then there isomorphism from G to a subgraph of G. We use the fact that every graph is a subgraph of itself using the identity map as the isomorphism. [The identity map is the one that takes every vertex to itself and every edge to itself].
The relation S is not symmetric. For instance K₃ is a subgraph of K₄ and yet K₄ is not a subgraph of K₃. [Note that to prove that a statement is false we only need to produce one instance where it is not true. An example that proves that a statement is false is called a counterexample.]
The relation is antisymmetric. [This means that for graphs in D, .] We have to show that if a graph H is a subgraph of G, and then G is not a subgraph of H. Let e(H) be the number of edges in H and v(H) the number of vertices in H. Similarly let e(G) be the number of edges in G and v(G) the number of vertices in G. If H is a subgraph of G then, bearing in mind that the isomorphism takes vertices of H to a subset of the vertices of G and edges of H to a subset of the edges of G, and that an isomorphism is one-to-one, we have that e(H) e(G) and v(H) v(G). Since , the isomorphism is not onto so either e(H) < e(G) or v(H) < v(G) . This means we can't have an isomorphism that takes vertices of G to a subset of the vertices of H and edges of G to a subset of the edges of H. Therefore G is definitely not a subgraph of H
The relation S is transitive. We have to show that if a graph F is a subgraph of G, and G is a subgraph of H, then F is a subgraph of H. If F is a subgraph of G, then there is an isomorphism f from F into G. Also if G is a subgraph of H then there is an isomorphism g from G to H. The composition gives us an isomorphism from F into H. So F is a subgraph of H.
An equivalence relation is one that is reflexive, symmetric, and transitive. A partial order is one that is reflexive, antisymmetric, and transitive. From what we have done is not an equivalence relation but it is a partial order.

K₅ has 10 edges, K₁₀ has 45 edges, and K₂₀ has 190 edges.

We prove by induction that the number of edges in K_n is ½ n(n-1)

Basis:
( n = 1 ) K₁ has 0 edges and

Induction:
We need to show that if i is a positive integer and K_i has ½ i (i - 1) edges then K_i+1 has ½ (i+1)(i) edges. Suppose that K_i has ½ i (i - 1) edges. To obtain K_i+1 from K_i we need to add a vertex and i edges (an edge from the new vertex to each of the i vertices that make up K_i. Therefore K_i+1 will have i more edges than K_i i.e., ½ i (i - 1) + i edges. This can be rewritten as

By induction it follows that K_n has ½ n (n-1) edges for n=1, 2, 3, ...

e-mail: C. Mawata