Question 1:

Determine if the problem is P or NP-Hard:

A) given graph G and a natural number k. does G has a k-star subgraph?

speculated answer - problem is in P,

for Graph G will create a table of size |V| (column i for vertex i), we will run through all of the edges of the graph, for an edge <Vi,Vj> and +1 to columns i and j.

such subgraph exists if one of the cells of the table is >=k. we run in time |E| (+|V| for counting the number if vertices) which is clearly in P.

B) given graph G and a natural number k, does G has an induced subgraph that has a k-star?

I have a (weird) feeling, this is also in P,

can someone please explain?