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
3answers
390 views

Restrictions on the faces of a $3$-regular planar graph

I'm new here and I'm having difficulty with this graph theory question. Suppose $G$ is a connected $3$-regular planar graph which has a planar embedding such that every face has degree either $5$ or ...
4
votes
1answer
401 views

Chromatic number $χ(G) > k$ implies existence of path of length $k$

Show that if $G$ is a loopless graph, $k≥1$ is an integer and $χ(G) > k$ then $G$ has a path with $k$ edges. So, we can assume WLOG that $G$ is connected. we're looking for a path $P$ where ...
3
votes
0answers
110 views

The minimal number of triangles or edges whose union is a graph $G$.

Let $G$ be a simple graph of order $n$. If $G$ is triangle-free, then we know that there is a bipartite graph of the same order and the same size. So $G$ has size less than $n^2/4$. Now if it has ...
6
votes
3answers
391 views

$n$-ary trees with $k$-internal nodes - Catalan numbers

It is known that the Catalan numbers count the number of binary trees with $k$-internal nodes. I was thinking of how to count ternary trees or in general $n$-ary trees with $k$ internal nodes and got ...
1
vote
1answer
2k views

Constructing A Hasse Diagram Using The Covering Relation

I am still having a little difficultly with the covering relation, specifically that when y covers x, $x \prec y$ there is no element in between them, $ x \prec z \prec y$, where x,y, and z are ...
0
votes
1answer
48 views

Individual components of flow along edges in a graph

I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = \{V,E\}$ with vertices $v \in V$ and directed edges $e_{i,j} \in E$. Each node has an ...
4
votes
3answers
274 views

Pólya's Enumeration formula and isomers

The hydrocarbon benzene has six carbon atoms arranged at the vertices of a regular hexagon, and six hydrogen atoms, with one bonded to each carbon atom. I know that two molecules are said to ...
1
vote
1answer
2k views

Difference between 'weak' and 'strong' connected (regarding directed graphs)

While studying discrete maths I was having difficult to understand the following definition: Here is a definition about connected graphs from the book Ralph Grimaldi - Discrete and Combinatorial ...
2
votes
0answers
151 views

The matrix $J$(all of whose entries are 1) is a polynomial in the adjacency matrix $A$ of a graph $G$ …

if and only if $G$ is connected and regular. To prove the "only if", assume $J$ is a polynomial in $A$. Then $JA=AJ$. The entries in the $i$th row of $AJ$ are all equal to the sum of the entries in ...
2
votes
1answer
436 views

A path has only two vertices which are not cut-vertices

Prove that a simple undirected graph $G$ is a path if and only if $G$ has exactly two vertices which are not cut-vertices. If $G$ is a path then it is obvious that there only two vertices which ...
2
votes
1answer
318 views

Pólya’s Enumeration Theorem and chemical compounds

The hydrocarbon naphthalene has ten carbon atoms arranged in a double hexagon, and eight hydrogen atoms attached at each of the corners of the hexagons. Naphthol is obtained by replacing one of ...
0
votes
1answer
80 views

Constant $f:[\mathbb{N}]^2\to \{1,2\}$.

Let $[\mathbb{N}]^2$ denote the set collection in size $2$. Now, let $f:[\mathbb{N}]^2\to \{1,2\}$. How can one show that, if we fixing some $n\in \mathbb{N}$, then there exist infinite set ...
0
votes
1answer
145 views

Breadth first search and bipartiteness

I was just wondering what the correlation is between a breadth-first search tree of a graph and that graph being bipartite?
5
votes
1answer
130 views

Bounds on an induced subgraph of a 4-critical graph

I just hate having to come here to ask questions. It's like accepting defeat that you can't solve it yourself.. but I've been trying to solve this for hours and can't find the intuition to solve the ...
2
votes
0answers
128 views

unique maxflow problem

Suppose we have a directed graph, and we want to get the maxflow out of this graph. How can we decide the maxflow of this graph is unique? I have an idea that after we found a maxflow out of the ...
6
votes
3answers
379 views

Are all $4$-regular graphs Hamiltonian

It is easy to show that all connected $2$-regular graphs are Hamiltonian. The Petersen graph is a $3$-regular graph that is not Hamiltonian. Are there any $4$ regular graphs that are not Hamiltonian? ...
0
votes
1answer
147 views

Smallest Imperfect Graph who's chromatic number equals clique number

So I need to find the smallest imperfect graph, $G$ who's chromatic number equals it's clique number. ie: $$\chi(G) = \omega(G)$$ Finding imperfect graphs isn't hard (since finding perfect graphs ...
3
votes
0answers
59 views

topology on a graphs space

Let $\mathcal{G}$ be the set of locally finite, connected rooted graphs $(G,v)$ up to isomorphism $\cong$. Denote by $[G,v]_r$ the sub-graph of $(G,v)$ induced by the vertices at distance $\leq r$ ...
0
votes
1answer
3k views

Prove by induction that every connected undirected graph with n vertices has at least n-1 edges

The problem is in the title. Here is the hint given: In the inductive case, try proof by contradiction. For this proof by contradiction, you may need to use the hand-shake lemma and concept of ...
0
votes
2answers
697 views

Proof related to minimum and maximum degree of vertices of an undirected graph

I don't know how to proceed for this problem. I would appreciate any help. Thanks! Let $\delta$ and $\Delta$ be the minimum and maximum degree of the vertices of an undirected graph G. Show ...
2
votes
2answers
352 views

Spanning trees implies isomorphism?

I'm having trouble solving this question: Prove or disprove the following statement: Given a graph G, if T and U are spanning trees of G, then T and U are isomorphic. I know that two graphs are ...
4
votes
1answer
447 views

Prove nonplanarity of a graph

So I'm working to prove that any graph $G=(V,E)$ with $|V|\geq11$ will either be nonplanar itself, or its complement $G^\complement$ will be nonplanar. My text says that to prove nonplanarity, one ...
2
votes
2answers
304 views

Bipartite Graph Counting.. Easy?

So.. Perhaps I'm misunderstanding this question, but it reads: How many nonisomorphic complete bipartite graphs $G = (V, E)$ satisfy $|V| = n \geq 2$? I mean.. Doesn't this just ask how many ...
1
vote
1answer
96 views

Empty Set Partition of a Bipartite Graph?

My textbook defines a bipartite graph in the following way: A graph $G = (V, E)$ is called bipartite if $V = V_1 \cup V_2$ with $V_1 \cap V_2 = \emptyset$, and every edge of $G$ is of the form ...
2
votes
1answer
363 views

How to prove in a graph $G$, its incidence matrix $A$ is totally unimodular if and only if $G$ is a bipartite graph?

I'm learning network and transportation model. The question is not from my homework. I'm just curious about: In a graph $G$, its incidence matrix $A$ is totally unimodular if and only if $G$ is a ...
1
vote
1answer
217 views

Unique path between any pair of vertices in $G$

I'm having trouble with this question: Suppose there is a unique path between any pair of vertices in $G$. Prove that $G$ is a tree. I know that a path is a trail where all vertices are distinct ...
6
votes
2answers
429 views

Can be a graph strongly connected but with undirected edges?

I'm studying graph theory and I'm facing the following question: What happens when you have a connected graph with directed and undirected edges? Is it strongly connected or not? With connected ...
4
votes
3answers
561 views

The inverse of the adjacency matrix of an undirected cycle

Is there an expression for $A^{-1}$, where $A_{n \times n}$ is the adjacency matrix of an undirected cycle $C_n$, in terms of $A$? I want this expression because I want to compute $A^{-1}$ without ...
2
votes
1answer
85 views

Need help on Intepretation of statements about Graph Theory

I'm studying basic graph theory, and my instructor gives me these statements to translate into pictures. I don't quite understand the meanings of the statements, but I have some thoughts about them. ...
2
votes
1answer
66 views

Proof of $\chi(G)\leq 1+\max_i\min\{d_i,i-1\}$ in graph theory

I am learning a coloring theorem in graph theory: If a graph $G$ has degree sequence $d_1\geq\cdots\geq d_n$, then $\chi(G)\leq 1+\max_i\min\{d_i,i-1\}$. The proof in the book consists of 4 ...
1
vote
0answers
23 views

Definition of Chromatic class digraph of a m-coloured digraph

I have to prove that if $D$ is a m-coloured digraph, then $K(D) = K\big(C(D)\big)$ Where $C(D)$ is the chromatic transitive closure of $D$, which is a multidigraph with the same nodes and arcs of $D$ ...
1
vote
2answers
240 views

Show that a matched set of nodes forms a matroid

Let $G=(V,E)$ denote a graph. We call a subset of nodes $V^\prime\subset V$ matched if there is a matching $M\subset E$ in $G$ such that $M$ contains all nodes in $V^\prime$. We define the family ...
1
vote
0answers
158 views

Can Hall's theorem be derived from Tutte–Berge formula?

Can Hall's theorem be derived from Tutte–Berge formula? Hall's theorem is for existence of X-saturated matching in a X,Y bipartite graph. Tutte–Berge formula is for maximum size of a matching: ...
2
votes
1answer
94 views

What structure does the set of all the matchings in a graph have?

In a graph, the class of all the sets of vertices that can be covered by some matching forms a matroid. I wonder what kind of structure the class of all the matchings in a graph can have? Or does it ...
1
vote
2answers
151 views

existence of a spanning tree

Let $T$ and $T'$ be two spanning trees of a connected graph $G$. Suppose that an edge $e$ is in $T$ but not in $T'$. Show that there is an edge $e'$ in $T'$, but not in $T$, such that ...
1
vote
1answer
62 views

Equivalence on the underlying set of a matroid?

Given a matroid $(S, F)$, $\forall x,y,z \in S$, if $\{x\}, \{y\}, \{z\} \in F$, $\{x,y\} \notin F, \{y,z\} \notin F$, will $\{x, z\} \notin F$? I can't figure this out by definition of matroid. ...
0
votes
1answer
664 views

M-ary tree problem

A full $m$-ary tree $T$ has 81 leaves and height 4 1) Give the upper and lower bounds for $m$ 2) What is $m$ if T is also balanced? [with $m^h=l$ for maximum leaf in a m-ary tree $m^4=81$ then m=3 ...
0
votes
2answers
190 views

Tree problem about preorder notation

Show that an ordered rooted tree is uniquely determined when a list of vertices generated by a preorder traversal of the tree and the number of children of each vertex are specified.
2
votes
2answers
342 views

Questions on Trees and Automorphisms of Trees

Please give me some hints for the following problems. Many thanks in advance. Problem 1. Let $T_1,\cdots, T_n$ be a finite set of subtrees of a tree $X$ and let $T_i\cap T_j\ne\emptyset$ for all $i$ ...
1
vote
1answer
59 views

Why does $S + o(G-S)$ have the same parity as $n(G)$?

I seemed to see this from some place I don't remember In a graph $G$, for any subset $S$ of vertices, $|S| + o(G - S)$ has the same parity (odd or even) as $n(G)$, by counting the vertices ...
0
votes
3answers
129 views

Largest number of bridges in any $k$-vertex graph

Hi, I'm very new to graph theory and have a question. For each positive integer $k$, what is the largest number of bridges in any $k$-vertex graph? Thanks.
9
votes
1answer
249 views

(Olympiad) Minimum number of pairs of friends.

I gave up, my approaches didn't work (induction, pigeon-hole, parity; though obviously there's a good chance I didn't use them cleverly): In a group of 12 people, every pair of them has a common ...
2
votes
1answer
115 views

Counting number of vertices given a graph

Given some graph $G$ such that we have between two vertices an edge, and between each edge two distinct vertices. How many vertices do we have if there is a total of 196 edges? I'm reproducing this ...
1
vote
2answers
167 views

100 roads in a city, 1 is closed

In a certain country, 100 roads lead out of each city, and one can travel along those roads from any city to any other. One road is closed for repairs. Prove that one can still get from any city to ...
0
votes
1answer
116 views

Disconnected graph with degree sequence

Is there a disconnected graph with degree sequence $(4$, $4$, $3, 3, 3, 3, 3, 3)$?
0
votes
1answer
721 views

Neighbours of a (subset of) vertex in a graph

In a graph G, are the neighbours of a vertex defined to exclude the vertex? Do we need to explicitly distinguish between "the neighbours of a vertex $v$" and "the neighbours of a vertex $v$ in $G - ...
5
votes
1answer
159 views

Almost all labeled graphs implies almost all graphs?

I would be thankful if someone could verify the following reasoning. Let $I$ be some graph property that is invariant (chromatic number, connectedness,etc.). Let $p(n)$ be the number of (labeled) ...
0
votes
3answers
466 views

Hypercube Maximum Distance, Graph Theory

I'm dealing with some hypercube questions here. The one I'm currently on states: Find the maximum distance between pairs of vertices in $Q_8$. Give an example of one such pair that achieves this. ...
1
vote
0answers
59 views

Finding expectation of size of a subgraph.

I have been trying to implement a algorithm but got stuck in finding expectation of the size of the subgraph. n - size of the network. d - at most number of communities a node could participate ...
0
votes
1answer
376 views

Graph Theory: Clique concepts

I was trying to solve a basic clique problem but i have stucked at some following points: ...