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

1
vote
1answer
39 views

What is the difference between a forest and a spanning forest?

If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree). If a graph is ...
0
votes
0answers
16 views

Matrix Representations of Chordal Graphs and Uses in Linear Algebra

Chordal graphs have the property of perfect elimination ordering. In Knuth's 2012 Christmas lecture ~1:12:10 he mentions that when the coefficients of a linear algebra problem can be written as a ...
0
votes
2answers
35 views

Planar complete tripartite graphs

For which values of $r$, $s$, and $t$ is the complete tripartite graph $K_{r,s,t}$ planar? Obviously I want to look for either a $K_5$ or a $K_{3,3}$ in order to show that a specific graph is ...
0
votes
1answer
68 views

Five-coloring plane graphs

These days I've been reading about graph coloring. Right now I'm dealing with the five color theorem. I know how to prove that every planar graph is 6 and 5 colorable. I'm looking on the proof of the ...
1
vote
0answers
34 views

How to answer the following question related to counting the number of trees of a graph?

I am asked to prove the equality $$ 2(n-1)n^{n-2} = \sum_{k=1}^{n-1} \binom{n}{k} k(n-k)T(k)T(n-k) , $$ where $T(k)$ is the number of different trees with $k$ numbered vertices. I think the ...
0
votes
1answer
16 views

Competion Problem in graph theory

How can I prove that every graph has two vertices which are endpoints of the same number of edges? Any hints?
1
vote
2answers
26 views

What is the time to create a complement of a graph?

It seems to me that the running time to make a complement of a graph with $n$ nodes is $n!$. Is there any way to make this running time polynomial? That is, is there any method to construct a ...
1
vote
0answers
25 views

Decentralized Algorithm for a one dimensional ring

I'm working on a homework in which a graph of n nodes is arranged as a one-dimensional ring and every node has 3 out-going edges. I need some help in proving that any decentralized algorithm would ...
1
vote
0answers
42 views

Graph where PageRank will not converge

I have been stuck on a homework problem for days. Construct a strongly connected graph in which the basic PageRank computation does not converge. I tried everything and still cannot find a ...
0
votes
1answer
23 views

Connected graph definition

It is correct to say that a connected graph is only when there exist some vertex that is connected to all other vertices? I think this is correct, because a connected graph not all vertices are ...
0
votes
0answers
20 views

probability in graphs - degree distribution

I am reading this paper on networks which employs probability in analyzing graphs. Suppose that a graph has $n$ vertices. Furthermore, if each vertex has a probability $p_k$ of having $k$ neighbors, ...
0
votes
2answers
62 views

How many trees are in the spanning forest of a graph?

Spanning forest is defined by the following definition: A forest that contains every vertex of G such that two vertices are in the same tree of the forest when there is a path in G between these two ...
0
votes
1answer
14 views

maximal independent set in a graph

Let $G$ be a graph and $A$ is a subset of vertex set of $G$. $A$ is said to be independent if for any $x, y \in A$, $(x,y) \notin E(G)$, i.e $x$ and $y$ not connected by an edge. Further A is said to ...
2
votes
1answer
105 views

Characterizing a certain set of matrices arising from binary trees

Suppose I have a binary tree, like v1 v4 \ / -------- / \ v2 v3 I can write a matrix for this tree whose $(i,j)$th ...
4
votes
2answers
96 views

Condition about regular graphs

I am trying to do this graph theory exercise: Let graph $G$ doesn't contain triangle and for each unconnected vertices of $G$ exists exactly two vertices that are neighbors of both. Show that ...
0
votes
1answer
22 views

Bipartite graphs, degrees and neighbors

Let $G = (X \cup Y, E)$ be a bipartite graph with no isolated vertices and let $S \subseteq X$. Suppose $|S| = |N(S)|$ (neighboors of $S$) and that $\forall \{x,y\} \in E$, where $x\in X$ and $y\in ...
1
vote
0answers
26 views

Proof of Euler Characteristic for Sphere

Theorem 1. All cell decompositions of a sphere $S$ have Euler characteristic 2. This is well-known, but I had this idea for an intuitive proof: for any cell decomposition $\Gamma$ with $V$ ...
1
vote
2answers
70 views

A combinatorics question on a $n \times n$ grid

In the book 'Foundations of Data Science' by Hopcroft and Kannan, they have the following exercise (Ex. 5.46): Let G be a $n \times n$ lattice and let $S$ be a subset of $G$ with cardinality at ...
2
votes
0answers
35 views

Interesting Questions in Spectral Graph Theory

In the past, I have worked on few problems in Spectral graph theory and their applications to Physics. I have read parts of Fan Chung's book and Daniel Spielman lecture notes. I really enjoyed the ...
1
vote
1answer
27 views

Show that $m \le 2e/v \le M$

$G$ be a graph with $v$ vertices and $e$ edges.Let $M$ be maximum degree of the vertices of $G$, and let $m$ be the minimum degree of the vertices $G$.Show that $$m \le 2e/v \le M$$ I am completely ...
0
votes
3answers
27 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 ...
-1
votes
0answers
37 views

The Petersen graph is vertex-transitive

How can you show that the Petersen Graph is vertex-transitive ? (You can't use the fact that the Petersen graph is isomorphic to any graph with vertices labelled $\binom{5}{2}$ where two vertices X ...
0
votes
2answers
66 views

Can you take off a sweater while wearing headphones?

This seems like a graph theory problem, but I'm not sure how to approach it. To clarify potential ambiguities, let's set up the situation. You are wearing a sweater (with one arm through each ...
0
votes
1answer
21 views

Understanding Kirchhoff's theorem

I am trying to the understand the Kirchhoff's theorem and it seems to be giving a hard time. Basically how do you explain why you have $n^{n-2}$ in finding the number of cycles in a given graph. A ...
1
vote
0answers
72 views

Number of Nodes within a Given Distance from a Node

Suppose we are given a $d$-regular graph $G=(V,E)$ of order $n$. Let $\lambda_2$ be the second-largest eigenvalue of $G$'s adjacency matrix. Does this information help obtaining a lowerbound or ...
2
votes
2answers
158 views

Help with graph induction proof

I'm trying to prove : Given a simple graph G with n vertices, where n is even, prove that if every vertex has degree n/2 + 1, then G must contain a (simple) 3-cycle. A (simple) 3-cycle is a set of 3 ...
1
vote
1answer
28 views

What multigraphs are isomorphic to their dual graph?

I arrived at this question by way of investigating knots, particularly the idea of "turning them inside out", in a sense. I called these their "complements". I noticed that the Borromean Rings ...
1
vote
0answers
22 views

Automorphism group of a bipartite regular graph

Showing an automorphism group of complete bipartite graph $K_{n,m}$ is easy. I'm wondering if there is an classification of automorphism groups of bipartite regular graphs. Did anyone heard something ...
2
votes
2answers
52 views

Software to find out adjacency matrix of a graph.

I am looking for a graph theoretical software. I can draw a graph delete or add its vertices and edges whatever I want. The software shall give me the Adjacency matrix, degree matrix etc. Is such a ...
-1
votes
2answers
49 views

Number of paths with length 3 in a wheel graph [closed]

How would I count the number of 3 length paths in a wheel graph where $n >= 2$?
2
votes
0answers
25 views

Existence of a Transversal in a Cycle

Let a transversal be defined as an independent set of $G$, containing precisely one vertex from each $V_i$. Let $G = (V,E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup \ldots \cup V_n$ be ...
0
votes
2answers
31 views

Finding paths in a graph with n vertices

Let n ≥ 2 be a natural number. Consider the graph G = (V, E) where V ={0,1,2,...,n} and E=({0,1},{0,2},...,{0,n}) ∪ ({1,2},...,{n−1,n}) ∪ ({n,1}) For paths, it's a sequence of (non-repeating) ...
0
votes
1answer
12 views

Removing a vertex from a non k-colorable graph cannot make it (k−2)-colorable

This is supposidly True in the key but a pentagon is non-4-colorable and removing a vertex (either deletion or contraction) leaves a 2 colorable graph. anyone know anything about this or is it just ...
0
votes
1answer
26 views

Proof for a graph distance

For Graph $G$, there are several $(x, y)$-paths; the shortest among them have length $2$. Thus $d(x, y) = 2$. Prove that graph distance satisfies the triangle inequality. That is, if $x,y,z$ are ...
0
votes
1answer
32 views

Simple Cycle Graph proof

How can I show/prove that given a simple graph G with $n$ vertices, where $n$ is even, that if every vertex has degree $\frac{n}{2} + 1$, then G must contain a (simple) 3-cycle
2
votes
1answer
50 views

Simple planar graph

What's the best way of proving this? ...
1
vote
1answer
35 views

Minimum degree and connectivity

Let $\delta$ denote the minimum degree of graph G. Show for every graph G, if G is connected and |V|>2$\delta$, then G has a path of length 2$\delta$. I started this way: Let P be the longest path ...
1
vote
1answer
60 views

Using Pigeonhole Principle for a graph proof

Using the Pigeonhole Principle, prove that in any graph with two or more vertices there must exist two vertices that have the same degree. (Note: the problem does not assume that the graph is ...
2
votes
1answer
24 views

Is there a name for a directed graph in which every vertex has outdegree one?

Per the question title, I'm dealing with a number of directed graphs, all of which are 1-out regular, and figure that there is probably a name for such a thing. Unfortunately, all my search attempts ...
0
votes
0answers
9 views

Find all vertices in a DAG with the property that none lie on any path with K edges and sum of weights ≥ Threshold

Given a DAG G with weights on the edges, all nodes have a blue color. We seek to color with red every path nodes with K edges such that the sum of weights of this path is greater than a threshold (T). ...
2
votes
1answer
30 views

Power of an adjacency matrix

For any adjacency matrix what does the power of it represent, you know like M^k ??? I guess what I'm wondering is, if I square it for example, what do the numbers correspond to??
0
votes
0answers
28 views

Diameter and maximal independent sets

I've proved that every nontrivial tree has at least two maximal indepndent sets, with equality only for stars via the bipartition of the trees. I am trying to extend that proof to general graphs, and ...
0
votes
1answer
29 views

Proving that a sub-graph of a tree is a tree

The proof that P ::== any sub-graph, G* of the tree G, is also a tree, involves proof by contradiction. We can suppose that the sub-graph has a cycle --> the whole graph has a cycle --> the whole ...
-6
votes
1answer
45 views

Discrete Math on Graphs [closed]

Can someone explain to me that how would I show that Is it possible for a simple graph with 6 vertices to have 42 edges?
-3
votes
1answer
38 views

Discrete Math On proving Graph Degree Sequence

Can someone please explain that how would I show or Prove that there is no graph with degree sequence (1, 1, 2, 3, 4, 4, 5, 7). Thanks
0
votes
1answer
19 views

Definition of a leaf in a tree

Across two different texts, I have seen two different definitions of a leaf 1) a leaf is a node in a tree with degree 1 2) a leaf is a node in a tree with no children The problem that I see with ...
1
vote
1answer
30 views

Elementary graph theory representation

We've been talking about graphs in class and my understanding is that $K_3$ means a graph $K$ has $3$ nodes. I have also been reading online to get a better understanding of what was said in class but ...
0
votes
2answers
31 views

Prove graph is bipartite

How can I prove that a graph $G = (V, E)$ is bipartite if and only if $G$ can be coloured with $2$ colors/colours? I know it's true, but don't know how to do it other than drawing every possible ...
2
votes
0answers
28 views

Maximum number of tile possible in 2048 game? [duplicate]

Ok my question is what is the maximum number of tile we can make in the 2048 game assuming we were really lucky and got all 4 number tiles and got the new squares exactly where we needed them?
2
votes
0answers
24 views

Probabilistic edge covers

Given a graph $G=(V,E)$ where every edge $ij$ has a corresponding probability $p_{ij}$. We can then consider random subsets of the edges $C \in E$ for which the probability that an edge $ij$ is ...