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
1answer
67 views

Spectrum of the sum of matrices

I have an $n$ by $n$ matrix $A$ such that: $$A = J_n + (k-1)I_n$$ $I_n$ being the identity matrix and $J_n$ the all-$1$ matrix. The spectra of those matrices are as follow: $$Spec(J_n) = (k^2 -k ...
0
votes
2answers
297 views

Necessary and sufficient condition for an Euler trail between two vertices

Graph theory question one of those obvious math proofs so its going to be a pain to prove. Show that G=(V,E) has an Euler trail between (different) vertices u and v if and only if G is connect and ...
0
votes
2answers
303 views

Trees and leaf: Graph Theory

Let T be a tree with at least two vertices and let $v \in V(T)$. If T-v is a tree, then v is a leaf. Attempt: Let T be a tree and let v be a leaf of T. Then T-v is a tree. Let $a,b \in V(T-v)$. We ...
0
votes
2answers
88 views

How can it be proved that each vertex can be at most in one strongly connected component in a directed graph?

How can it be proved that each vertex in a directed graph will exactly be in at most one strongly connected component? I do not see it in the graph below which I think contains a couple of connected ...
0
votes
2answers
63 views

plane or planar graph

I am bit confused with graph theory terms. Could you please tell me, if I say plane embedded graph embedded plane graph what is correct. Also, If i use either 1 or 2 (the correct ...
0
votes
1answer
390 views

Induction on Menger's theorem by Diestel in Graph Theory

How does exactly the induction go in the proof number one? What is the induction hypothesis there and what is the induction step? By the induction hypothesis, $G/e$ contains an $A–B$ separator ...
0
votes
3answers
1k views

Isomorphism between two particular graphs

Are these two graphs isomorphic?
0
votes
1answer
47 views

Graphs containing specific edges

Can someone please walk me through how to solve this? Determine the number of graphs on $10$ vertices labeled $1, 2, \cdots, 10$ that contain exactly two out of the following four edges $e_1 = \{1, ...
0
votes
1answer
824 views

Hamiltonian Cycle Problem

At the moment I'm trying to prove the statement: $K_n$ is an edge disjoint union of Hamiltonian cycles when $n$ is odd. ($K_n$ is the complete graph with $n$ vertices) So far, I think I've come ...
0
votes
2answers
80 views

Match covered graph is 2-connected

Seems to be an easy question, but I can't find the right direction. Let $G$ connected graph on at least 4 vertices, such that every edge in it, participates in a perfect matching. Prove that $G$ is ...
0
votes
2answers
82 views

What is the most basic graph, and how would you use it in an induction-proof?

Can a single point be a graph? Or is it just a single edge and two vertices? How do you apply this to an induction-proof in graph-theory? thanks
0
votes
2answers
1k views

k×k grid has tree-width at least k

I am looking for ideas how to solve the problem from Diestel's textbook Graph Theory. Chapter 12. Minors, Trees, and WQO. Problem 16. Apply Theorem 12.3.9 to show that the $k \times k$ grid has ...
0
votes
1answer
614 views

Edge coloring of a $k$-regular bipartite graph

Let $G$ be a $k$-regular bipartite graph. I want to prove that I can color the edges of $G$ with at most $k$ colors. I want to do this without using König's theorem. Ideally I would like to prove ...
0
votes
3answers
171 views

Finding graph node positions based on edge weights

Let's say I have a complete weighted graph with $n$ nodes and strictly positive weights. I'd like to find the smallest $d\in\mathbb{N}$ such that there exists a set of $n$ points in ...
0
votes
1answer
218 views

Vertex Invariants for a 2-regular Graph

If i have a graph in this form (adjacency matrix): 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 This is a 2-regular graph with 7 vertices. What ...
0
votes
1answer
28 views

Extension of hypercube

I understand the notion of a hypercube as a graph with vertex set $\{0,1\}^{n}$ and an edge between two vertices if their vertices differ in one co-ordinate is there an extensive body of work on the ...
0
votes
1answer
23 views

Brook's theorem. Where I make a mistake?

please explain me one thing: According to Brook's theorem $ \chi(G ) \le \deg(u) $ But it can't be true. After all, there are $\deg(u) + 1 $ colors and I'm enclosing a draw. ...
0
votes
1answer
41 views

How many nonisomorphic graphs are there with 10 vertices and 43 edges?

How would I go about solving this? I know that $K_{10}$ has $9+8+7+\dots+1=45$ edges. So would it be something like $\binom {45}{43}$ because out of the 45 total edges, one must choose 43 for the ...
0
votes
1answer
53 views

Modification of the Ramsey number

Let us denote by $n=r(k_1,k_2,\ldots,k_s)$ the minimal number of vertices such that for every coloring of the edges of the complete graph $K_n$ by $s$ different colors, there is some color $1\le i\le ...
0
votes
2answers
36 views

Proof. Theory graph. Please check.

If graph $G = (V,E) $ where $|V| = n $ is connectivity then $ n-1 \le |E| $ My proof: The our thesis is: $ \forall G $ is connectivity $\Rightarrow$ $ n-1 \le |E| $ I prove that using 'reductio ...
0
votes
2answers
27 views

Counting non-isomorphic graph.

How many exists non-isomorphic 4-regular graphs $G = (V,E)$ where $|V|=7$ vertices? I'm asking for hint to solve it with group theory( if it is possible) and without them
0
votes
2answers
31 views

Assign integers to the vertices of $G$

Let $G=(V,E)$ be a directed acyclic graph. I have to write an algorithm to assign integers to the vertices of $G$ such that if there is a directed edge from vertex $i$ to vertex $j$, then $i$ is less ...
0
votes
1answer
67 views

Chromatic number proof verification

Prove that $χ(G) ≤ 1 + \text{max}\{\text{deg}_{G} (x): x ∈ V\}$ holds for every (finite) graph $G = (V, E)$. Let's consider the worst case for graph colouring. To obtain the maximal case, we connect ...
0
votes
2answers
37 views

All non-isomorphic graphs with chromatic number 4

I need to find all non-isomorphic graphs $G=(V,E), |V|=5$ with chromatic number $\chi(G) = 4$. How do I do that?
0
votes
1answer
13 views

Connecting nodes under certain conditions and trying to find the correct sequence on OEIS to describe the situation.

I would like to construct graphs under the following conditions: No loops Maximum of one edge between any nodes Connected No intersection between the edges may occur on a plane. Now, a similar ...
0
votes
1answer
24 views

Definition of connected graph

The definition of a connected graph states that: A graph $G$ is called connected provided for each pair $a,b$ with $a\neq b$ of vertices $\exists$ a walk joining a and b.(equivalently a chain joining ...
0
votes
1answer
25 views

Definition of a tree and 2 cycles

I've run into a problem with the definition of a tree, and possibly more generally with the definition of a cycle. I've run into the problem a few sections after we talked about trees, and I never ...
0
votes
3answers
41 views

Acyclic graph must have a leaf

It is a theorem that every acyclic graph must have a leaf, ie. A vertex with degree 1 at most. Intuitively, it makes sense as any vertex with more degree would be connected to at least 2 vertices ...
0
votes
1answer
27 views

True false question related to graph having a unique Minimum weight spanning tree

You have an undirected graph $G$ $G$ has a cycle in it That cycle has an edge $e$ e is a unique lightest weight edge in that cycle Is it true that $e$ is part of every Minimum weight spanning tree ...
0
votes
1answer
94 views

For a Cycle Graph is there only one Spanning tree?

For example a Cycle Graph C200 has only 1 spanning tree right? Because adding just one edge to a spanning tree will create a cycle?
0
votes
1answer
25 views

Let $G$ be a disconnected graph of order $n \geq 6$ having three components. Prove that $\Delta(\overline G) \geq \frac{2n}{3}$

Let $G$ be a disconnected graph of order $n \geq 6$ having three components. Prove that $\Delta(\overline G) \geq \frac{2n}{3}$ This is what I got let $u \in V(G)$, since $G$ have three components, ...
0
votes
2answers
35 views

Prove that $G$ is Hamiltonian.

Let $G=(V,E)$ be a connected graph which is not a tree. Prove that if for every cycle $C$ of the graph G and for any $v \in V(G)- V(C)$ there are more than $\frac{|C|}{2}$ edges from $v$ to $V(C)$ ...
0
votes
3answers
77 views

Proof verification: a connected graph always has a vertex that is not a cut vertex

Prove that every connected graph has vertices that even when you remove them, the graph stays connected. Let's assume that $\delta(G)>1$ becuase if it is equal to 1, the proof is trivial. I will ...
0
votes
1answer
61 views

What is a `red vertex` and what is a `blue vertex`?

I showed the following question on an exam: let $G(V, E)$ connected indirected graph with positive weights. any vertex is colored with either blue or red. Claim: if edge $(u, v)$ is the ...
0
votes
2answers
44 views

In a 2-connected simple graph, is there always a simple cycle containing any given path P and disjoint edge e?

For any finite simple graph $G$ which is 2-connected, given a path $P$ and a disjoint edge $e$, is it true that there is always a simple cycle containing $P$ and $e$? If instead of an edge $e$, a ...
0
votes
2answers
32 views

Number of spanning trees of a graph (behind the formula)

Given $G$ a subgraph of $K_n$ s.t. $G$ has $n$ vertices with adjacency matrix $A$; why is $$\sum_{T \text{ spanning tree of }K_n}\prod_{(i,j)\in T}A_{i,j}$$ the number of spanning trees? I can't get ...
0
votes
1answer
31 views

Why doesn't the Back and Forth Method for Infinite Random Grap use the Axiom of Choice?

A way to proof that any two Rado graphs (countably infinite nodes, has graph extension property) are isomorphic, is to use the back and forth method. At each step of the method, we have a vertex $v$ ...
0
votes
2answers
40 views

In Dijkstra algorithm, it takes the source, what about the sink?

I'm studying the Dijkstra algorithm, but in my book, the algorithm takes as input only the graph and the source. Why it doesn't ask for the destination vertex? How can it work? Thanks a lot.
0
votes
1answer
134 views

How many triangles are see in complete K5 graph

How many triangles are on picture below? On yahoo answers I have found that numbers of triangles in complete graph with n nodes is: $\frac{n(n-1)(n-2)}{6}$ But how this formula has been estimated? ...
0
votes
4answers
27 views

For trees with $10$ vertices, consider those which have a vertex of degree $8$. What is the number of such trees?

I'm trying to figure out what is the flaw in my thinking for this practice question. If a tree has $10$ vertices, one of which must have degree of $8$, this means that we essentially have a $K_{1,8}$ ...
0
votes
1answer
26 views

Minimum k-spanning tree including a given node

Given a Graph (V, E), it is very easy to find the minimum spanning tree using Kruskal's Algorithm. A k-minimum spanning tree is restricted to k nodes, and finding it is actually NP-hard. However, ...
0
votes
1answer
26 views

Irreducible graph on a sphere

I am trying to grasp an article about the kissing problem in three dimensions (Das Problem der dreizehn Kugeln, by K. Schütte and B.L. van der Waerden). The article deals with irreducible graphs on a ...
0
votes
1answer
113 views

Proving Graphs Properties (common neighbors)

I'm struggling with two different-but similar questions. I'm pretty new with the subject so will really appreciate explanation on how to approach these kind of question Prove that in every 10 ...
0
votes
1answer
38 views

Transform any graph to bipartite graph

Is there any method which can transform any graph to bipartite graph? For example, if I were given a graph, in order to make it to become bipartite, I can delete vertices which lie in the two vertices ...
0
votes
3answers
140 views

Wolf cabbage and goat using dijkstra.

A farmer has to cross a river with a wolf, a goat and a cabbage. He has a boat, but in the boat he can take just one thing. He cannot let the goat alone with the wolf or the goat with the cabbage. ...
0
votes
1answer
40 views

Which of the following graphs have Euler curcuits, Euler trails, or neither?

Which of the following graphs have Euler curcuits, Euler trails, or neither? I tried :Euler Trails [A,B,C,A,D,B,C] I tried :Euler Trails [A,B,D,E,G,F,D,C,A,D,G] but I am confused about Euler ...
0
votes
1answer
68 views

What's maximal clique?

I'm unable to understand what maximal clique is. I mean how a clique can't be extended by a node and remain a clique? If I add a node and then I connect this node to every other nodes in the clique, ...
0
votes
1answer
162 views

Determining the total degree of a tree

At the start of the solution, I understand that any tree with four vertices has three edges. I don't understand the next statement: "Thus the total degree of a tree with four vertices must be 6." ...
0
votes
2answers
47 views

Vertex/Edge Independence Proof

Show, for every connected graph $G$ of order $6$ with four independent vertices, that either $\alpha(G)=5$ or $\alpha'(G)\geq2$. I was thinking about using a contradiction proof. Any hints?
0
votes
3answers
35 views

Proving the distance between 2 vertices

Let $G$ be a disconnected graph. Then, I know $\bar G$ is connected. Prove that if $u$ and $v$ are any two vertices of $\bar G$, then $d_{\bar G}(u,v)=1$ or $d_{\bar G}(u,v)=2$ Then I also know if ...