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.

learn more… | top users | synonyms

0
votes
0answers
23 views

Depth First Search example and detailed explanation

I need some clarification on how the depth first search algorithm works on a matrix. It doesn't seem all the intuitive to me and the assignments seem quite arbitrary. Can anyone perhaps explain it ...
0
votes
0answers
19 views

A question about minimally 3-connected graphs

How to prove that each cycle in a minimally 3-connected graph must contain at least two vertices of degree three?
2
votes
2answers
54 views

Is this an NP-Complete problem? (unweighted & undirected graph)

G is an unweighted, undirected graph. Then, I cannot prove that [deciding whether G has a path of length greater than k] is NP-Complete. How can I show whether the algorithm is NP-complete or not?
2
votes
2answers
58 views

Definition of Aut(G) in the graph theory and group theory

For a fixed group G, we define the collection of group automorphisms is the automorphism group Aut(G) in the group theory. (An automorphism: a permutation on the set G) In the graph theory, on the ...
1
vote
1answer
34 views

A nontrivial tree such that its complement is a maximal planar graph

A nontrivial tree $T$ of order $n$ has the property that its complement $\overline{T}$ is a maximal planar graph (i.e., a planar graph such that adding any edge makes it nonplanar). (a) What is $n$? ...
0
votes
0answers
10 views

Prove that $\overline{cr}(C_3 \square C_t)=t$ for $t\geq3$.

Prove that $\overline{cr}(C_3 \square C_t)=t$ for $t\geq3$. I understand that this is true because when you draw the edges of the inner most cycle and the outer most cycle the edges will cross the ...
0
votes
0answers
36 views

determining the values for id(v) and od(v) in directed graph using counting flag method

I'm working on this problem: Let $G=(V,E)$ be a directed graph, where $|V|=n$ and $|E|=e$. What are the values for $\sum_{v\in V} id(v)$ and $\sum_{v\in V} od(v)$? This is a question that requires ...
1
vote
1answer
56 views

how to show that when an edge is removed from K5, the resluting subgraph is planar.

this question might be simple to others, but I'm stuck on this question. "prove that when I deleted an edge from $K5$, it has planar sub-graph . So, I know that G is planar if and only if G contains ...
0
votes
1answer
20 views

If $K_n$ is super-magic, what is the sum at each vertex?

If $K_n$ is super-magic, what is the sum at each vertex? A super-magic labeling of a graph is an edge weighting where the edge weights are consecutive integers (that’s the super part), and where if ...
0
votes
1answer
18 views

Question on Breadth First Search.

Lets assume there is a directed graph A -> B -> C -> D -> A. Now won't the Breath First Search tree contain a back edge but everywhere it states a Breath First Search tree can't contain a back edge. ...
0
votes
1answer
28 views

Cuts and cycles in graph, edges in common [closed]

If there is a cycle C and a cut set S in a connected graph G then C and S have even number of common edges.
2
votes
1answer
59 views

Question on Graph Connectivity

Now this question is on graph connectivity and I still can't get my head around these graph theory questions. Now we've been given an n-node graph which is represented by $G=(V,E)$ and two nodes $s$ ...
1
vote
1answer
56 views

Algorithm to find max no. of nodes that can be visited

Given an undirected non-weighted graph edges. '1#2', '2#3', '1#11', '3#11', '4#11', '4#5', '5#6', '5#7', '6#7', '4#12', '8#12', '9#12', '8#10', '9#10', '8#9' where ...
5
votes
0answers
90 views

Original Research Topics for High School Student [closed]

I'm a grade 12 student interested in Number Theory, Graph Theory and Combinatorics and I am currently looking for ideas for an original research project/paper in mathematics. I was hoping that someone ...
0
votes
1answer
30 views

Question related to toplogical sorting

Now the question is related to online banking. It states that like in online banking for security banks never ask the whole password but instead they may ask for 3 random numbers in their password. ...
0
votes
0answers
10 views

Let $d_1,d_2,…,d_n$be positive integers, with $n\geq 2$. Prove that there exists a tree with vertex [duplicate]

Let $d_1,d_2,...,d_n$ be positive integers, with $n\geq 2$. Prove that there exists a tree with vertex degrees $d_1,d_2,...,d_n$ if and only if $\sum d_i= 2n-2$. I have no idea how to prove this ...
1
vote
0answers
26 views

(Proof Verification) Prove There Is A Hamiltonian Cycle for Every $n$ dimensional hypercube where $n\geq2$

Prove There Is A Hamiltonian Cycle for Every $n$ dimensional hypercube where $n\geq2$ My book gave a very fancy proof by induction, but to me it seems obvious that if we simply follow the standard ...
0
votes
1answer
50 views

Create a schedule using a graph-theoretic model

For the next Olympic Winter Games, the organizers wish to expand the number of teams competing in curling. They wish to have 14 teams enter, divided into two pools of seven teams each. Right now, ...
1
vote
0answers
7 views

Approximation for the minimal test cover / minimal group test problem

There are multiple approximation methods I find for the minimal test cover, where approximation is with respect to the size of the test set. However I am looking for approximation which starts with a ...
0
votes
0answers
33 views

Graph theory and minor relation

I'm having some confusion with proposition $1.72$ of the Diestal book on Graph Theory which states that (ii) If $\Delta(X) \leq 3$, then every $MX$ contains $TX$ thus every minor with maximum degree ...
2
votes
1answer
46 views

Every 2-connected graph has a cycle of at least length 5

Is it true that every 2-connected simple graph of at least 10 vertices has at least one cycle of length 5 or more? I know that any two vertices lie on a common cycle and I am trying to use this by ...
2
votes
2answers
37 views

Deriving the number of edges in a Turán graph

When stating Turán's theorem, the Turán graphs are often used to give an upper bound on the possible number of edges in a graph without a clique of a certain size. This bound can also be proven ...
0
votes
1answer
34 views

Graph theory question, probably connected to Ramsey Theorem

Is the following statement true or false? For every $n > 0$, such $N$ exists, that no matter how we "color" all of the subsets of the set with $N$ elements(we only use two colors), No matter how ...
1
vote
0answers
29 views

Graph theory question about distances

Prove, that for every $n$, a $K(n)$ exists, that no matter how I place $K(n)$ points in the plane, there will always be at least $n$ different distances, that are specified with those points. My ...
4
votes
0answers
60 views

What is this relation on the set of paths called in graph theory?

Suppose I have a directed simple graph $\Gamma$ (no edge loops or multi-edges) and a directed path $v_0v_1\cdots v_k$ joining vertex $s=v_0$ to vertex $t=v_k$. By directed path I mean that each pair ...
5
votes
0answers
44 views

A game may related to graph theory or topology

Last Sunday, I played a game with a group of people. The game is as follows: A group of people form a circle as shown below: Each person must remember how he/she is linked with his two neighbours. ...
2
votes
2answers
24 views

possible polyhedra from euler's formula

I'm not very clear with the euler's formula, and I couldn't find it anywhere. I'm sorry if it is a double post. F + V - E = 2 Is the euler's formula. If the equation balances, is it polyhedra all ...
11
votes
3answers
282 views

Elementary Combinatorial Proofs using group action

In trying to prove that the number of spanning trees in $K_5$ is $125$ I adopted the following method: Let $S$ be the set of all such spanning trees and let $S_5$ act in a natural way on $S$. Now ...
0
votes
0answers
20 views

Graph Theory: Describing the maximum weight spanning tree

The question states, "Describe an algorithm for finding a spanning tree of maximum weight for a given weighted graph. Prove that your algorithm works." I researched and what I only know so far is ...
2
votes
2answers
28 views

Weakly connected graph test

What is the right algorithm for testing whether the graph is "weakly connected"? The theory says: Oriented graph $G=(V,E)$ is weakly connected graph if and only if for every two vertices $u,v \in ...
0
votes
1answer
64 views

Question related to Directed Acyclic Graphs

In an assignment I got a question, "Show that the strongly connected component of a DAG is also a DAG." Now I wasn't able to solve this. The problem I faced with this question was that the DAG is ...
-1
votes
2answers
47 views

On 2- player game.

Consider the following 2-player game: you start with n tokens on a table, in a single pile. Players alternate turns. On a player's turn, they must choose one pile of their choice, and split it into ...
0
votes
0answers
30 views

Prove that Hall's Condition is necessary for complete matching

Here's what I have so far: Hall's Algorithm states that given $n$ girls and $n$ boys a complete matching between the two groups is possible iff any of the three conditions are satisfied: There is ...
0
votes
1answer
31 views

Proof approach: A 7x7 matrix with 15 ones can allow at least three marriages

This is quite difficult to prove imho with regards to Hall's Marriage Algorithm I can visualize a number of scenarios that work (i.e. put ones from the first entry to the fifteenth, or across ...
0
votes
1answer
59 views

Using Hall's Theorem to show something.

Suppose that there are five young women and five young men on an island. Each man is willing to marry some of the women on the island and each woman is willing to marry any man who is willing to marry ...
1
vote
1answer
67 views

Prove that if G is a graph with no even cycles, then every cycle in G is an induced subgraph.

I tried using the contrapositive to prove the original statement: If no cycle in G is an induced subgraph, then G is a graph with no odd cycles. To prove this, I assumed that G did have an odd cycle ...
1
vote
1answer
13 views

How many edges could a cross-section of a polyhedron have?

We know that the cross-section of a cube could have 3, 4, 5, or 6 edges. But there could be no more. This can be explained in many ways: (1) The number of edges of a cross-section can't exceed the ...
0
votes
1answer
38 views

Maximum edge of a directed graph , if it contains weak components?

A digraph includes n nodes , and has two weak components , what is the maximum number of edges? ( there is no directed cycle)? Another question ,how does the answer change , if there is two strong ...
2
votes
1answer
109 views

Furthest distance vertices undirected tree

I know in my mind that it's very obvious, but I just can't seem to prove the following statement: Let $G$ be an undirected non-trivial tree with at least $3$ vertices. Let $u$ be an arbitrary vertex ...
1
vote
1answer
34 views

Planar Graph faces

let $G$ be a planar graph Prove that in any planar embedding of $G$, number of faces with odd degree is even. Also, prove that if G is not bipartite, then there are at least 2 faces with odd degree. ...
0
votes
1answer
25 views

Graph skeleton for thorus $S_1$

Suppose the $g=1$ platonic graph with degree $d=3$ and the number of edges bounding each face is $n=6$ ($v=14$). Is this the skeleton of $S_1$ (the thorus with one hole)? We know that $K_7$ and the ...
1
vote
1answer
21 views

Deriving the probability of a node (vertex) on the end of a random chosen link (edge) having degree d.

From Jackson - Social and Economic Networks p. 87 (link: http://press.princeton.edu/chapters/s4_8767.pdf p.12 in pdf): (...) (T)he distribution of degrees of a node found by choosing a link ...
4
votes
1answer
62 views

Number of subgraphs in the ladder graph

Assume you have the usual (in both directions infinite) ladder graph. I can try to provide a picture if needed. Further assume the vertices are labelled and I have one distinct vertex (call it the ...
0
votes
0answers
41 views

Modifying Kruskal's algorithm for Maximum Spanning Tree

So in our class, we did a proof on Kruskal's algorithm for finding Minimum Spanning Tree. Now, based on that, I have to modify it to find me a Maximum Spanning Tree. I know the idea, taking ...
2
votes
1answer
22 views

Let $r\geq 4$ and let $\delta (G)> (1-\frac{1}{r-1})|G|$. Show that every edge is contained in a $K_r$

Let $r\geq 4$ and let $\delta (G)> (1-\frac{1}{r-1})|G|$. Show that every edge is contained in a $K_r$ Hint: Pick the remaining vertices of the $K_r$ one by one. I'm at a loss as to what to do, ...
2
votes
1answer
68 views

How many subgraphs does a $4$-cycle have?

Question: How many subgraphs does a $4$-cycle have? I am trying to discover how many subgraphs a $4$-cycle has. I know that there will be $2^4=16$ subgraphs with no edges, but I am not sure how to ...
1
vote
1answer
44 views

Collection of spanning trees for a simple connected graph

Consider a graph $G$ whose edges are labelled $\{1, 2, ..., k\}$. Then the set of spanning trees is a collection of subsets of $[k]$. a) Let $T$ = $\{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}$. Can $T$ be ...
0
votes
0answers
19 views

Best set of subgraphs of a weighted complete bipartite graph

Consider a weighted complete bipartite graph, i.e. consider the graph $G=(V,E)$, with $V=X \cup Y$, $X \cap Y = \emptyset$ and $E = X \times Y$, and a set of weights $W=\{w_i : i \in E\}$. Now we ...
1
vote
2answers
26 views

Proof related to maximum degree of node in a graph

So I'm given this problem - Prove that in every graph with 25 vertices, in which holds that in every 3-subset of vertices, at least two of them are connected, there exists a node of degree at least ...
0
votes
1answer
22 views

Hamiltonian circuit in a Hamming graph

The problem is exactly what I have asked here: Showing that a particular graph is Hamiltonian Let $Q:=\{1,2,\ldots, q\}$. Let $G$ be a graph with the elements of $Q^n$ as vertices and an edge ...