# complete bipartite subgraph of a graph

• Sep 6th 2011, 04:47 PM
wik_chick88
complete bipartite subgraph of a graph
(a) prove that every graph of order \$\displaystyle n \geq 4\$ and size \$\displaystyle n + 1\$ contains \$\displaystyle K_{1,3}\$ as a subgraph

(b) describe the graphs of order \$\displaystyle n \geq 4\$ and size \$\displaystyle n\$ that do not contain \$\displaystyle K_{1,3}\$ as a subgraph
• Sep 6th 2011, 05:13 PM
Plato
Re: complete bipartite subgraph of a graph
Quote:

Originally Posted by wik_chick88
(a) prove that every graph of order \$\displaystyle n \geq 4\$ and size \$\displaystyle n + 1\$ contains \$\displaystyle K_{1,3}\$ as a subgraph

(b) describe the graphs of order \$\displaystyle n \geq 4\$ and size \$\displaystyle n\$ that do not contain \$\displaystyle K_{1,3}\$ as a subgraph

I see that you have some other postings, more than 170.
You should understand by now that this is not a homework service nor is it a tutorial service. Please either post some of your own work on these problems or explain what you do not understand about the question.