1. Determine whether P4 is an induced subgraph of K4,4. If yes, then exhibit it.

Question

1. Determine whether P4 is an induced subgraph of K4,4. If yes, then exhibit it. If no, then explain why not.

2.Complete the proof from class (missing pieces are starred):

[] If G contains no odd cycles, then G must be bipartite.
Proof. Take any given vertex, call it a and define the following sets:

X={vV(G) : there is an even path between a and v}

Y ={vV(G) : there is an odd path between a and v}

Claim 1: The sets X and Y are disjoint.
Suppose X and Y intersect. Consider x X Y .

Claim2: Any edge has the form xy with xX and yY.

Suppose there is an edge of the form x1x2 with x1 and x2 in X.

***Use the same example to derive a contradiction.

Explanation / Answer

Solution :- (1)

K4 is not a subgraph of K4,4.
To prove this, denote by X, Y the two parts of K4,4.
For each subgraph H of K4,4 with four vertices, some number of its vertices are in
X and the rest are in Y . We have the following options:
V(H) X or V(H) Y . Then H must have no edges because a bipartite graph
has no edges both of whose endpoints are in X (respectively, Y ). So H is not K4.
Three vertices from H are in X and one is is Y (or vice versa). Then at most one
of the vertices in H has degree at most 3 and the rest of the vertices have degree
at most 1. But, the degree sequence of K4 is 3, 3, 3, 3. So, H is not K4 in this case
either.
Two vertices from H are in X and two are in Y . Then the maximum degree of a
vertex in H is 2, and H is not K4.
Since we considered all possible subgraphs of K4,4 with four vertices and none of them
could be K4, K4 is not a subgraph of K4,4.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.