# Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

135 views

### Does this graph contain $K_5$ or $K_{3,3}$ as subdivision or minor?

Does this graph contain subdivision of $K_5$ or $K_{3,3}$? Does this graph contain $K_5$ or $K_{3,3}$ as minor? I'm not sure if I'm correct, but I think the answer is yes for both questions. $K_5$...
953 views

### Can I find the connected components of a graph using matrix operations on the graph's adjacency matrix?

If I have an adjacency matrix for a graph, can I do a series of matrix operations on the adjacency matrix to find the connected components of the graph?
90 views

126 views

### Graph Theory: prove the defect version of Hall's theorem

i don't really understand the expression delta(A), and i don't understand how exactly and in what way i am supposed to bound the matching number of G.
74 views

### G is a bipartite graph, where for every edge e=(a,b)[a,b are in A,B] d(a)>d(b), and d(a)>0, show that there is a matching saturating A

I think the direction is definitely HALL, i tried using induction on the size of S, where S is some subgroup of A, but i wasn't able to complete the process.
65 views

### Showing that a graph doesn't contain a Hamiltonian ccle

In the article here it says that A Hamilton circuit cannot contain a smaller circuit within it. ? What is meant by this? I thought this meant that for example if ...
2k views

### Maximum no.of edges in a bipartite graph

I have to prove that for a bipartite graph G on n vertices the number of edges in $G$ is at most $n^2/4$. I used induction on n. induction hypothesis:Suppose for a bipartite graph with less than ...
44 views

### MST or not without children ?

I've got an undirected weighted graph G with c:E(G)->IR. Now I want to find a spanning tree, such that a node v arbitrary, shall be an internal node, and among all spanning trees, in which v is only ...